Valid Sudoku

Problem

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.

Solution

Approach: Hash Sets for Rows, Columns, and Boxes

The key insight is to use hash sets to track seen numbers in each row, column, and 3x3 box. We iterate through the board once, and for each non-empty cell, we check if the number already exists in the corresponding row, column, or box sets. If it does, the board is invalid.

The tricky part is calculating which 3x3 box a cell belongs to. We can use integer division: box_index = (row // 3, col // 3).

Implementation

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    continue

                num = board[r][c]
                box_index = (r // 3) * 3 + (c // 3)

                # Check if number already exists in row, col, or box
                if num in rows[r] or num in cols[c] or num in boxes[box_index]:
                    return False

                # Add number to sets
                rows[r].add(num)
                cols[c].add(num)
                boxes[box_index].add(num)

        return True

Alternative (Using Single Set with Tuples):

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        seen = set()

        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    continue

                num = board[r][c]

                # Create unique identifiers for row, col, and box
                row_key = (num, 'row', r)
                col_key = (num, 'col', c)
                box_key = (num, 'box', r // 3, c // 3)

                if row_key in seen or col_key in seen or box_key in seen:
                    return False

                seen.add(row_key)
                seen.add(col_key)
                seen.add(box_key)

        return True

Complexity Analysis

Time Complexity: O(1) - We always iterate through exactly 81 cells (9×9), which is constant.
Space Complexity: O(1) - We use at most 9 sets with at most 9 elements each, which is constant space.

Key Insights

Box Index Calculation: The formula (row // 3) * 3 + (col // 3) maps each cell to its 3×3 box (numbered 0-8). This is crucial for checking box validity efficiently.
One Pass Solution: We can validate all three constraints (row, column, box) in a single pass through the board by maintaining separate sets for each.
Early Return: As soon as we find a duplicate in any row, column, or box, we can immediately return false without checking the rest of the board.
Set vs Array: Using sets for O(1) lookup is more efficient than using arrays/lists which would require O(n) linear search.
Tuple Keys Alternative: The single-set approach uses tuples to create unique keys for each constraint type, which can be more elegant but uses the same amount of space.