36. Valid Sudoku

Problem Link

To check if a sudo board is valid, you've to satisfy 3 types of criteria: - each row shouldn't have repeating digit. - each column shouldn't have repeating digit. - each box (3x3 here) shouldn't have a repeating digit.

This can be checked pretty easily using hash maps (similar to contains_dupliacte).

How would you map cells within a box to same key?

\(key=(floor(row/3))*3 + (floor(col/3))\)

Pseudocode

• Iterate over the board using two loops. Within each iteration, if the cell isn't .
• check if the value is present in your hashmap buckets.
  • if present, we can say the sudoku is invalid and return.
  • else add the values to respective hashmap key.

Runtime Complexity

number of elements in board -> n

Time: \(O(n)\), single iteration over each element with constant time checks.

Space: \(O(n)\) <- from hashmaps.

PythonGo

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)
        cols = defaultdict(set)
        box = defaultdict(set)
        for r in range(len(board)):
            for c in range(len(board[0])):
                cell = board[r][c]
                b = (r // 3) * 3 + c // 3
                if cell == ".":
                    continue
                elif cell in rows[r] or cell in cols[c] or cell in box[b]:
                    return False

                rows[r].add(cell)
                cols[c].add(cell)
                box[b].add(cell)
        return True

func isValidSudoku(board [][]byte) bool {
    var rows, cols, boxes [9][9]bool

    for r := range board {
        for c := range board[0] {
            cell := board[r][c]
            if cell != '.' {
                b := (r/3)*3 + (c / 3)
                idx := int(cell - '1')
                if rows[r][idx] || cols[c][idx] || boxes[b][idx] {
                    return false
                }
                rows[r][idx] = true
                cols[c][idx] = true
                boxes[b][idx] = true
            }
        }
    }
    return true
}

---