Problem Statement

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

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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.

Additional information

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

Example 1:

Input: board =
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","8",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","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

Hash Set (One Pass)

Intuition
To determine if a Sudoku board is valid, we simply need to check the three rules: no duplicates in rows, no duplicates in columns, and no duplicates in 3x3 sub-grids. We can iterate through every cell in the 9x9 grid once. For every number we encounter, we check if we have seen it before in its corresponding row, column, or sub-grid.

We can use hash sets (dictionaries in Python) to store the numbers we have seen. To uniquely identify the sub-grids, we can use the coordinate pair (r // 3, c // 3).

Algorithm

1. Initialize a collection of sets for rows, columns, and sub-grids.
2. Iterate through the board using nested loops for r (row) and c (column).
3. If the current cell is empty (.), continue to the next cell.
4. If the current number is already in the corresponding row set, column set, or square set, return False.
5. Add the current number to the corresponding row set, column set, and square set.
6. If the loops finish without returning False, the board is valid, so return True.

def is_valid_sudoku(board: list[list[str]]) -> bool:
  
    rows = defaultdict(set)
    cols = defaultdict(set)
    squares = defaultdict(set)  # key = (r // 3, c // 3)

    for r in range(9):
        for c in range(9):
            if board[r][c] == ".":
                continue
            
            if (board[r][c] in rows[r] or
                board[r][c] in cols[c] or
                board[r][c] in squares[(r // 3, c // 3)]):
                return False
            
            rows[r].add(board[r][c])
            cols[c].add(board[r][c])
            squares[(r // 3, c // 3)].add(board[r][c])
            
    return True

Time & Space Complexity

• Time complexity: O(1)

• Reason: Since the board size is fixed at 9x9, we always perform a constant number of operations (81 iterations).

• Space complexity: O(1)

• Reason: In the worst case, we store 81 numbers in our sets. Since the board size is fixed, this is technically constant space.

Array with Bitmasking

Intuition
Instead of using sets to store seen numbers, we can use integers as bitmasks. Each bit in an integer can represent whether a number (1-9) has been seen. For example, the k-th bit is set if the number k has been encountered. This reduces space overhead significantly compared to hash sets.

Algorithm

1. Initialize arrays of integers rows, cols, and squares of size 9.
2. Iterate through the board.
3. For each number n at (r, c), convert it to an integer val.
4. Calculate the box index k = (r // 3) * 3 + (c // 3).
5. Check if the val-th bit is set in rows[r], cols[c], or squares[k].

• To check: (mask >> val) & 1

6. If the bit is set, return False.
7. Otherwise, set the val-th bit in all three masks.

• To set: mask |= (1 << val)

8. Return True if no duplicates are found.

def is_valid_sudoku(board: list[list[str]]) -> bool:
    rows = [0] * 9
    cols = [0] * 9
    squares = [0] * 9

    for r in range(9):
        for c in range(9):
            if board[r][c] == ".":
                continue
            
            val = int(board[r][c]) - 1
            pos = 1 << val
            box_idx = (r // 3) * 3 + (c // 3)
            
            if (rows[r] & pos) or (cols[c] & pos) or (squares[box_idx] & pos):
                return False
            
            rows[r] |= pos
            cols[c] |= pos
            squares[box_idx] |= pos
            
    return True

Time & Space Complexity

• Time complexity: O(1)

• Reason: Fixed number of operations for a 9x9 board.

• Space complexity: O(1)

• Reason: We use fixed-size integer arrays (constant space).