Framework Thinking - Neetcode 150 - Valid Sudoku
1. Understand the problem
-
Goal: Given a 9×9 board with digits ‘1’–’9’ or ‘.’ for empty, determine if the board is valid.
-
Validity rules:
-
Each row must not contain duplicate digits (ignoring ‘.’).
-
Each column must not contain duplicate digits.
-
Each 3×3 sub-box must not contain duplicate digits.
-
-
Important clarifications (state them to interviewer if not given):
-
The board is partially filled (contains ‘.’), not necessarily solvable.
-
We only need to check validity of the current state, not to solve the Sudoku.
-
Digits outside ‘1’–’9’ should be considered invalid input (defensive check).
-
-
If interviewer pushes, mention constraints: board is fixed 9×9 so algorithm is effectively O(1), but generalizing to n×n gives O(n²).
2. Ask clarifying questions
-
Are empty cells denoted by ‘.’? (If not, ask their sentinel.)
-
Do we need to validate characters outside ‘1’–’9’? (Should we return False for invalid chars?)
-
Should we treat the problem as fixed 9×9 or generalize to n×n? (Affects how you speak about complexity.)
-
Is it enough to return True/False, or do you want the conflict location for debugging?
3. Work through examples
- Example A — simple valid:
row0: ["5","3",".",".","7",".",".",".","."]
...
→ returns True
- Example B — duplicate in row:
board[0] contains two "5" → invalid → returns False
- Example C — duplicate in column:
board[0][0] = "8" and board[1][0] = "8" → invalid → False
- Example D — duplicate in 3×3 box:
Top-left box has two "9"s → invalid → False
Edge cases:
-
All dots (empty board) → valid (True).
-
Invalid char like ‘0’ or ‘a’ → treat as invalid input → return False (if interviewer expects validation).
-
Notes: Lookup in hash-set is O(1).
4. Brainstorm 2-3 solutions
4.1. Brute force check
-
For every filled cell, scan its row, column, and box (each check up to 9 elements).
-
Complexity: O(81 * 9) ≈ constant but ugly; code repeats logic.
4.2. Use sets for rows, columns, boxes (standard / optimal)
-
Maintain 9 sets for rows, 9 sets for cols, 9 sets for boxes.
-
For each filled cell (r,c) with value v:
-
Compute box_idx = (r//3)*3 + (c//3).
-
If v in rows[r] or cols[c] or boxes[box_idx] → invalid.
-
Else add v to these sets.
-
-
Notes: Lookup in hash-set is O(1).
-
Complexity: O(81) time (single pass), O(81) space worst-case (constant for 9×9).
4.3. Bitmask optimization (space micro-opt)
-
Use integers (bits 1–9) to represent seen digits per row/col/box.
-
Slightly faster and uses less space, but unnecessary complexity for 9×9 and less readable in interview unless asked => Still O(81).
5. Implement solutions
5.1. Brute force
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
for row in range(9):
seen = set()
for i in range(9):
if board[row][i] == ".":
continue
if board[row][i] in seen:
return False
seen.add(board[row][i])
for col in range(9):
seen = set()
for i in range(9):
if board[i][col] == ".":
continue
if board[i][col] in seen:
return False
seen.add(board[i][col])
for square in range(9):
seen = set()
for i in range(3):
for j in range(3):
row = (square//3) * 3 + i
col = (square % 3) * 3 + j
if board[row][col] == ".":
continue
if board[row][col] in seen:
return False
seen.add(board[row][col])
return True
-
Time complexity: O(81×9) => O(N^3).
-
Space complexity: O(1)
5.2. Hash Set (One Pass)
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
cols = defaultdict(set)
rows = defaultdict(set)
squares = 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
-
Idea: Lookup in hash-set is O(1).
-
Time complexity: O(N^2).
-
Space complexity: O(N^2).
5.3. Bitmask
class Solution:
def isValidSudoku(self, 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
if (1 << val) & rows[r]:
return False
if (1 << val) & cols[c]:
return False
if (1 << val) & squares[(r // 3) * 3 + (c // 3)]:
return False
rows[r] |= (1 << val)
cols[c] |= (1 << val)
squares[(r // 3) * 3 + (c // 3)] |= (1 << val)
return True
-
Time complexity: O(N^2).
-
Space complexity: O(N) => Because you treat 000000001 as number to store.
6. Explain for Bitmask solution
6.1. Bitwise AND (Check bit existed)
mask = 0b00010100 # digits 3 and 5 seen
bit = 0b00010000 # digit 5
mask & bit = 0b00010000 ≠ 0 ✅ means already seen
6.2. Bitwise OR (with assignment)
rows[r] = 0b00010100 # currently {3,5}
bit = 0b00100000 # digit 6
rows[r] |= bit → 0b00110100 # now {3,5,6}
6.3. Why index in block is (r//3)∗3+(c//3)
(4,4) (1,1) 1*3+1 4
6.4. What rows[0] or cols[0] or squares[0] store
rows[0] = 0b00010000 # In binary view
rows[0] = 16 # In decimal view
7. Test your code
- Initialize:
rows = [0,0,0,0,0,0,0,0,0]
cols = [0,0,0,0,0,0,0,0,0]
squares = [0,0,0,0,0,0,0,0,0]
- Step 1: (r=0, c=0, val=”5”)
val = 5 - 1 = 4
mask = 1 << 4 = 0b00010000
box = (0 // 3) \* 3 + (0 // 3) = 0
Check:
(mask & rows[0]) → (0b00010000 & 0b00000000) = 0 ✅
(mask & cols[0]) → (0b00010000 & 0b00000000) = 0 ✅
(mask & squares[0]) → (0b00010000 & 0b00000000) = 0 ✅
No duplicates → set the bits:
rows[0] |= 0b00010000 → rows[0] = 0b00010000
cols[0] |= 0b00010000 → cols[0] = 0b00010000
squares[0] |= 0b00010000 → squares[0] = 0b00010000
- Step 2: (r=0, c=1, val=”3”)
val = 3 - 1 = 2
mask = 1 << 2 = 0b00000100
box = 0
Check:
(mask & rows[0]) → (0b00000100 & 0b00010000) = 0 ✅
(mask & cols[1]) → (0b00000100 & 0b00000000) = 0 ✅
(mask & squares[0]) → (0b00000100 & 0b00010000) = 0 ✅
No duplicates → mark seen:
rows[0] |= 0b00000100 → rows[0] = 0b00010100
cols[1] |= 0b00000100 → cols[1] = 0b00000100
squares[0] |= 0b00000100 → squares[0] = 0b00010100
Now row 0 has digits 3 and 5 → rows[0] = 0b00010100