Valid Sudoku
Check that no digit repeats in any row, column or 3×3 box of a partly filled Sudoku board.
- Encoding constraints as set keys
- Hash set membership
Before this, know: 2D arrays (a list of rows), Hash sets (Set in JavaScript, set in Python), Integer division (// in Python, Math.floor in JavaScript)
A Sudoku board is a 9 × 9 grid. Some cells hold a digit "1" to "9"; empty
cells hold ".". The board is stored as a 2D array: an array of 9 rows, where
each row is an array of 9 cells. board[r][c] is the cell in row r and column
c, both counted from 0.
The board is valid when no digit appears twice in:
- the same row,
- the same column, or
- the same 3 × 3 box (the nine bold-bordered squares).
Return true if the filled cells follow these rules, false otherwise.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 5 | 3 | 7 | ||||||
| 1 | 6 | 1 | 9 | 5 | |||||
| 2 | 9 | 8 | 6 | ||||||
| 3 | 8 | 6 | 3 |
The rules that matter:
- Only the filled cells are checked. Empty cells are ignored.
- The board doesn’t have to be solvable. We only check for repeats.
- The digits are stored as strings (
"5", not5).
Each of those guest lists is a hash set: a collection that answers “is this value in here?” in about one step. We need 9 row sets, 9 column sets and 9 box sets: 27 sets in total.
The tricky part is knowing which box a cell is in. The boxes are numbered 0 to 8, left to right and top to bottom, and the formula is:
box = (r // 3) * 3 + (c // 3)
Here // means integer division: divide and throw away the remainder
(7 // 3 is 2). r // 3 tells us which band of three rows we’re in (0, 1 or 2),
and c // 3 which stack of three columns (0, 1 or 2). Each band holds 3 boxes,
so we multiply the band by 3 and add the stack.
Pause and think
(8, 0): band 8 // 3 = 2, stack 0 // 3 = 0, so box 2 × 3 + 0 = 6 (bottom-left).
(2, 5): band 2 // 3 = 0, stack 5 // 3 = 1, so box 0 × 3 + 1 = 1 (top-middle).
For every filled cell, scan the other 8 cells of its row, the other 8 of its
column and the other 8 of its box, looking for the same digit. One loop variable
k from 0 to 8 visits the k-th cell of each unit at once.
Brute force: scan row, column and box for every digit
Two 5s in the same box
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 5 | 3 | |||||||
| 1 | 5 | ||||||||
| 2 | |||||||||
| 3 | |||||||||
| 4 | |||||||||
| 5 | |||||||||
| 6 | |||||||||
| 7 | |||||||||
| 8 |
- k
- 0
- cells looked at
- 3
- Digit we're checking
- Cells compared at this k
- Same digit found
Checking 5 at (0, 0), k = 0: look at (0, 0) in its row, (0, 0) in its column and (0, 0) in its box. No other 5. (3 cells looked at so far.)
Which line is running?
function isValidSudoku(board) { for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const d = board[r][c]; if (d === ".") continue; // empty cell: nothing to checkRunning now: for (let k = 0; k < 9; k++) { // k-th cell of the same row, the same column and the same box const br = Math.floor(r / 3) * 3 + Math.floor(k / 3); const bc = Math.floor(c / 3) * 3 + (k % 3); if (k !== c && board[r][k] === d) return false; if (k !== r && board[k][c] === d) return false; if ((br !== r || bc !== c) && board[br][bc] === d) return false; } } } return true;}Brute force: scan the three units
function isValidSudoku(board) { for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const d = board[r][c]; if (d === ".") continue; // empty cell: nothing to check for (let k = 0; k < 9; k++) { // k-th cell of the same row, the same column and the same box const br = Math.floor(r / 3) * 3 + Math.floor(k / 3); const bc = Math.floor(c / 3) * 3 + (k % 3); if (k !== c && board[r][k] === d) return false; if (k !== r && board[k][c] === d) return false; if ((br !== r || bc !== c) && board[br][bc] === d) return false; } } } return true;}def is_valid_sudoku(board): for r in range(9): for c in range(9): d = board[r][c] if d == ".": continue # empty cell: nothing to check for k in range(9): # k-th cell of the same row, the same column and the same box br = (r // 3) * 3 + k // 3 bc = (c // 3) * 3 + k % 3 if k != c and board[r][k] == d: return False if k != r and board[k][c] == d: return False if (br, bc) != (r, c) and board[br][bc] == d: return False return TrueThe two lines computing br and bc find the k-th cell of the box: the box’s
top-left corner is at ((r // 3) * 3, (c // 3) * 3), and k walks across it 3 cells
per row.
Each filled cell makes 24 reads: the other 8 cells of its row, of its column and
of its box. (k runs 9 times with 3 checks each, which is 27, minus the 3 times
k lands on the cell itself.) A full board has 81 cells, so
up to 81 × 24 = 1,944 cell reads. The board is always 9 × 9, so technically this is a
fixed amount of work. But if the board were n × n, every cell would scan about
3n others: n² cells × 3n. In Big-O notation (a short way of saying how the
work grows as the input grows; see
Big-O in 5 minutes) that’s O(n³). The better
idea does each cell in a handful of lookups.
The brute force keeps re-reading the board to answer “is there already a 5 in this row?”. Instead we can remember the answer as we go: each rule (“no repeat in row r”) becomes a set, and the fact “5 is in row 0” becomes an entry in that set.
Pattern
Encoding constraints as set keys
Use it when: several rules must hold at once, and each rule is 'no repeats within some group'.
Signal words
- “valid sudoku”
- “no repeats in each row/column”
- “each group must be unique”
- “N-Queens”
- “placed already”
- Make 9 empty sets for rows, 9 for columns and 9 for boxes.
- Visit every cell, row by row. Skip empty cells (
"."). - For a digit
dat(r, c), work out its box:b = (r // 3) * 3 + c // 3. - If
dis already inrows[r],cols[c]orboxes[b], returnfalse. - Otherwise add
dto all three sets. - If we finish the board, return
true.
Press Play. The shaded cells are the row, column and box of the current cell; below the board you see exactly those three sets and the lookups. Start with LeetCode’s invalid example: the top-left cell is an 8, and box 0 already has another 8 further in. Then try the row and column clashes, where a different set catches the repeat. The last example runs the whole valid board (with check and add shown as one step to keep it short).
One pass with 27 sets
LeetCode example 2: the top-left cell is 8 instead of 5
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 8 | 3 | 7 | ||||||
| 1 | 6 | 1 | 9 | 5 | |||||
| 2 | 9 | 8 | 6 | ||||||
| 3 | 8 | 6 | 3 | ||||||
| 4 | 4 | 8 | 3 | 1 | |||||
| 5 | 7 | 2 | 6 | ||||||
| 6 | 6 | 2 | 8 | ||||||
| 7 | 4 | 1 | 9 | 5 | |||||
| 8 | 8 | 7 | 9 |
- r
- —
- c
- —
- d
- —the digit
- b
- —
- answer
- —
- Cell we're checking
- Its row, column and box
- Repeated digit
- Just added to a set
Make 27 empty sets: one per row, one per column and one per 3×3 box. Each set will remember which digits that unit already contains. We only check the filled cells; empty ones ('.') are skipped.
Which line is running?
function isValidSudoku(board) { // 9 sets for the rows, 9 for the columns, 9 for the 3x3 boxesRunning now: const rows = Array.from({ length: 9 }, () => new Set()); const cols = Array.from({ length: 9 }, () => new Set()); const boxes = Array.from({ length: 9 }, () => new Set()); for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const d = board[r][c]; if (d === ".") continue; // empty cell: nothing to check const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); // box 0..8 if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) { return false; // d is already in this row, column or box } rows[r].add(d); cols[c].add(d); boxes[b].add(d); } } return true;}One pass with 27 sets
function isValidSudoku(board) { // 9 sets for the rows, 9 for the columns, 9 for the 3x3 boxes const rows = Array.from({ length: 9 }, () => new Set()); const cols = Array.from({ length: 9 }, () => new Set()); const boxes = Array.from({ length: 9 }, () => new Set()); for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const d = board[r][c]; if (d === ".") continue; // empty cell: nothing to check const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); // box 0..8 if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) { return false; // d is already in this row, column or box } rows[r].add(d); cols[c].add(d); boxes[b].add(d); } } return true;}def is_valid_sudoku(board): # 9 sets for the rows, 9 for the columns, 9 for the 3x3 boxes 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): d = board[r][c] if d == ".": continue # empty cell: nothing to check b = (r // 3) * 3 + c // 3 # box 0..8 if d in rows[r] or d in cols[c] or d in boxes[b]: return False # d is already in this row, column or box rows[r].add(d) cols[c].add(d) boxes[b].add(d) return TrueLines 1–8 match in both languages. Python spreads the “skip empty cell” check over two lines, so from there on its line numbers run one ahead.
- Line 1: define the function. (LeetCode:
var isValidSudoku = function(board)in JS,def isValidSudoku(self, board)inclass Solutionin Python.) - Lines 3–5: 27 empty sets, 9 in each list.
Array.from({ length: 9 }, () => new Set())and[set() for _ in range(9)]both create nine separate sets.rows[2]will hold the digits already seen in row 2. - Lines 6–7: visit every cell, row by row.
- Line 8: read the cell. It’s a string such as
"5"or".". - Line 9 (JS) / lines 9–10 (Python):
continueskips the rest of the loop body for an empty cell and moves to the next one. - Line 10 (JS) / line 11 (Python): the box number. JavaScript has no
//, so we writeMath.floor(r / 3), which rounds down the same way. - Line 11 (JS) / line 12 (Python): three lookups, about one step each.
If any finds
d, the board breaks a rule. - Line 12 (JS) / line 13 (Python): return
falseat the first repeat. - Lines 14–16 (both): record
din its row, column and box sets. - Last line: no repeats anywhere, so the board is valid.
Instead of 27 sets, you can use one set and put the unit into the key itself:
"5 in row 0", "5 in col 0", "5 in box 0". Each filled cell makes three keys;
if any key already exists, a rule is broken. It’s the same logic, written as
“encode the constraint as a key”.
One set with descriptive keys
function isValidSudoku(board) { const seen = new Set(); // one set, with the unit written into the key for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const d = board[r][c]; if (d === ".") continue; const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); const keys = [`${d} in row ${r}`, `${d} in col ${c}`, `${d} in box ${b}`]; for (const key of keys) { if (seen.has(key)) return false; seen.add(key); } } } return true;}def is_valid_sudoku(board): seen = set() # one set, with the unit written into the key for r in range(9): for c in range(9): d = board[r][c] if d == ".": continue b = (r // 3) * 3 + c // 3 for key in ((d, "row", r), (d, "col", c), (d, "box", b)): if key in seen: return False seen.add(key) return TrueIn Python the key is a tuple like ("5", "row", 0), which a set can store
directly.
The first few filled cells of LeetCode’s invalid example (an 8 at (0, 0)):
| cell | d | box | in rows[r]? | in cols[c]? | in boxes[b]? | result |
|---|---|---|---|---|---|---|
| (0, 0) | 8 | 0 | no | no | no | add 8 to row 0, col 0, box 0 |
| (0, 1) | 3 | 0 | no | no | no | add 3 |
| (0, 4) | 7 | 1 | no | no | no | add 7 |
| (1, 0) | 6 | 0 | no | no | no | add 6 |
| (1, 3) … (1, 5) | 1, 9, 5 | 1 | no | no | no | add each |
| (2, 1) | 9 | 0 | no | no | no | add 9 |
| (2, 2) | 8 | 0 | no | no | yes | return false |
At (2, 2) neither row 2 nor column 2 has an 8 yet, so the first two lookups
pass. But boxes[0] already holds the 8 from (0, 0): both cells sit in the
top-left box. (Column 0 also has two 8s, at (0, 0) and (3, 0), but we stop at the
first broken rule we meet.)
Brute force
Time
O(1) here, O(n³) for an n × n board
Each of 81 cells reads 24 others: at most 1,944 reads. For an n × n board that grows like n² × 3n.
Space
O(1)
Only a few loop variables.
27 sets
Time
O(1) here, O(n²) for an n × n board
Each of 81 cells does 3 lookups and 3 inserts, about 6 steps: under 500 steps. For n × n it's proportional to the number of cells.
Space
O(1) here, O(n²) in general
At most 81 digits, each stored in 3 sets.
Because a Sudoku board never grows, both are technically O(1). Say so in an interview, then explain how each would scale for an n × n board. That shows you understand what Big-O measures.
What to say out loud, in this order:
- “Three rules: unique per row, per column, per box. Only filled cells count.”
- “I’ll keep a set per row, column and box. The box index is
(r // 3) * 3 + c // 3.” - “One pass: for each digit, three lookups and three inserts.”
- “The board is fixed at 9 × 9, so it’s O(1), or O(n²) for an n × n board.”
Likely follow-up questions:
- “Can you do it with one set?” Yes: encode the unit in the key (shown above).
- “Can you use bits instead of sets?” Each unit can be a 9-bit number where bit d is set when digit d is present. Same idea, smaller memory.
- “Now solve the Sudoku.” That’s Sudoku Solver, a backtracking problem, and these same three sets make each “can I place d here?” check instant.
Related problems:
- Contains Duplicate (this week): one set, one rule. Valid Sudoku is 27 of those at once.
- Group Anagrams (this week): designing the right key is the whole trick there too.