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 could be partially filled, where empty cells are filled with '.'.
Example 1:
Input:board = (valid 9×9 grid)
Output:true
Each row, column, and 3×3 box contains digits 1-9 without repetition.
Example 2:
Input:board = (grid with duplicate 8 in first column)
Output:false
The digit '8' appears twice in the first column.
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'
Hints
Hint 1Three constraints must all hold — track each independently.▼
You need to ensure no digit repeats in any row, any column, or any 3×3 box. These are three independent constraints. What data structure answers "have I seen this value before" in O(1)? A Hash Set.
Hint 2Maintain one set per row, per column, and per box.▼
Use three defaultdict(set) structures — one indexed by row number, one by column number, one by box key. For each filled cell at (r, c), check all three sets simultaneously before inserting. A single duplicate triggers an immediate False.
Hint 3The box key is just (r // 3, c // 3).▼
Integer division maps any cell to one of 9 boxes: (r//3, c//3) gives values (0,0) through (2,2). This is the exact key for your squares dictionary. The total work is always 81 cells regardless of input — O(1) effective complexity.
Brute Force Approach
O(81²) Time
🔄
Three Separate Passes
Time O(81²)Space O(1)
The naive approach validates each constraint in a separate nested loop — one pass for rows, one for columns, one for boxes. This is triple the work of the optimal approach but conceptually simpler.
1For each row, scan all 9 cells and check for duplicates.
2For each column, scan all 9 cells and check for duplicates.
3For each of the 9 boxes, scan all 9 cells and check for duplicates.
4Three O(81) passes = O(243) ≈ O(1) but with 3× constant overhead vs optimal.
defisValidSudoku(board):
# Check rowsfor r inrange(9):
seen = set()
for c inrange(9):
if board[r][c] != ".":
if board[r][c] in seen: returnFalse
seen.add(board[r][c])
# ... repeat for cols and boxesreturnTrue
Optimal Approach — Hash Set Constraints
O(81) Time
🗺️
Single Pass Triple Constraining
Time O(81) = O(1)Space O(81) = O(1)
A Sudoku board is exactly 81 cells. We can traverse the matrix exactly once, maintaining 3 separate Hash Sets for our three constraints: Rows, Columns, and 3x3 Squares.
1Initialize three collections of sets: rows, cols, and squares.
2Iterate through all (r, c) coordinates in the 9x9 grid.
3If the cell is filled, check if its value exists in rows[r], cols[c], or squares[(r//3, c//3)]. If it does, return False immediately.
4Otherwise, add the value to all three corresponding sets and continue!
if val in rows[r] or val in cols[c] or val in squares[(r//3, c//3)]:
returnFalse
rows[r].add(val)
cols[c].add(val)
squares[(r//3, c//3)].add(val)
returnTrue
Time Complexity Analysis
Outer loopsO(9 × 9) = O(81)Two nested loops iterate over all 81 cells of the fixed 9×9 board. The board dimensions are constants — they never grow with input size.
Per-cell workO(1)Each cell does 3 hash set lookups and up to 3 inserts. Hash set operations are O(1) average. The box key (r//3, c//3) is computed in O(1).
TotalO(1) time & space81 cells × O(1) work = O(81) = O(1). The board is always 9×9 regardless of which digits are filled in — no input can make this slower.
Insight: Valid Sudoku is one of the rare problems where every approach that visits each cell once is equally optimal — O(1) time and space are the ceiling and the floor. The only meaningful optimization is reducing the constant (e.g., using bit masks instead of sets to reduce memory by ~10×).
Discussion
…