Core Insight Trade one linear scan for a small lookup structure so each value is handled once.
Common Pitfall Do not overwrite information you still need before checking the current value.
Description
Determine if a 9x9 Sudoku board is valid.
Constraints
- Time Complexity:
O(1) - Space Complexity:
O(1)
Tags
arraymatrixhash-set
Implementation Plan Translate the invariant into these small, testable moves.
- Create the lookup structure.
- Scan each value once.
- Check the needed relationship before updating state.
- Return as soon as the answer is determined.
def isValidSudoku(board):
cols = collections.defaultdict(set)
rows = collections.defaultdict(set)
squares = collections.defaultdict(set)
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
cols[c].add(board[r][c])
rows[r].add(board[r][c])
squares[(r // 3, c // 3)].add(board[r][c])
return True