algoadvance

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated following these 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

The Sudoku board could be partially filled, where empty cells are denoted by the character '.'.

Example:

Input:
[
  ["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

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.

Clarifying Questions

1. Can the board contain invalid characters outside ‘1’-‘9’ and ‘.’?
   • No, the board will only contain the characters ‘1’-‘9’ and ‘.’.
2. Is the size of the board always fixed to 9x9?
   • Yes, the given Sudoku board is always 9x9 in size.

Strategy

To validate the board, we need to check three main constraints:

1. Each row should have unique digits.
2. Each column should have unique digits.
3. Each 3x3 sub-box should have unique digits.

We can achieve this by using three sets of hash sets:

• One for tracking digits in each row.
• One for tracking digits in each column.
• One for tracking digits in each 3x3 sub-box.

We’ll iterate over each cell in the 9x9 board, and for each non-empty cell, we’ll check the constraints. If any constraint fails, we return False. If no constraints fail, we return True.

Code

Here’s the implementation:

def isValidSudoku(board):
    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
            val = board[r][c]
            box_index = (r // 3) * 3 + (c // 3)
            
            if val in rows[r] or val in cols[c] or val in boxes[box_index]:
                return False
            
            rows[r].add(val)
            cols[c].add(val)
            boxes[box_index].add(val)
            
    return True

Time Complexity

• Time Complexity: O(1) because we are only iterating through the cells of a fixed 9x9 board, resulting in a constant number of operations.
• Space Complexity: O(1) for the same reason. The space used by the sets and other variables does not scale with input size, as it is fixed at 9x9.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?