Appearance
4.4.8 — Valid Sudoku
LeetCode 36 · Medium
The problem
Check whether a partly filled 9×9 Sudoku board breaks any rule. Each row, each column, and each 3×3 box must have no repeated digit. Empty cells are '.' and are ignored.
You are only checking the board as it stands. You are not checking whether it can be solved. A board with no repeats is valid even if no legal solution exists from there. Misreading this is the trap.
In plain English, given a 9x9 grid, check if any row, column, or 3x3 sub-grid contains a duplicate digit from 1 to 9. We don't care if the puzzle is actually solvable, just if the currently filled numbers are legal.
The pattern
Nine rows, nine columns, nine boxes — twenty-seven groups. For each one the question is "has this digit already appeared in this group?"
That is 4.4.1 again, twenty-seven times. So the interesting part is not the duplicate check. It is naming the group a cell belongs to, and two of the three names are obvious while the third is not.
Think of it like sorting students into clubs. A student (digit) belongs to a Row club, a Column club, and a Box club. If any club gets the exact same student twice, the board is invalid. All we need to do is keep an attendance sheet (hash set) for every single club, and every time we see a student, we check if they've already signed that club's sheet.
- Row group of cell
(r, c): justr. - Column group: just
c. - Box group: needs a formula.
The box index
The boxes form a 3×3 grid of boxes. Integer-divide each coordinate by 3 to find which one.
Rows 0–2 give box-row 0, rows 3–5 give box-row 1, rows 6–8 give box-row 2. Same for columns. That gives a pair (r//3, c//3), each part 0 to 2.
You can use that pair as a dictionary key directly. Or flatten it to a single number:
\text{box} = 3 \times \left\lfloor \frac{r}{3} \right\rfloor + \left\lfloor \frac{c}{3} \right\rfloor
Three times the box-row, plus the box-column. That is the row-major address formula from 4.2 — the same arithmetic the hardware uses to find array[i][j] in flat memory.
Check the formula rather than trusting it. (0,0) → 0 ✓. (8,8) → 8 ✓. (2,3) → 3·0 + 1 = 1, top-middle ✓. (3,2) → 3·1 + 0 = 3, middle-left ✓. Those last two catch a formula written the wrong way round.
The solution
python
from collections import defaultdict
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows, cols, boxes = defaultdict(set), defaultdict(set), defaultdict(set)
for r in range(9):
for c in range(9):
v = board[r][c]
if v == '.':
continue
b = (r // 3) * 3 + (c // 3)
if v in rows[r] or v in cols[c] or v in boxes[b]:
return False
rows[r].add(v)
cols[c].add(v)
boxes[b].add(v)
return Truets
function isValidSudoku(board: string[][]): boolean {
const rows = Array.from({ length: 9 }, () => new Set<string>());
const cols = Array.from({ length: 9 }, () => new Set<string>());
const boxes = Array.from({ length: 9 }, () => new Set<string>());
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const v = board[r][c];
if (v === '.') continue;
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) return false;
rows[r].add(v);
cols[c].add(v);
boxes[b].add(v);
}
}
return true;
}A cell belongs to a row and a column and a box at the same time, so the digit joins three sets. Check all three before inserting into any of them, or the cell matches itself.
Two small language points. Math.floor is needed in JavaScript because / gives a float, and 4/3 used as an index would silently give undefined. And use Array.from({length: 9}, () => new Set()), not new Array(9).fill(new Set()) — the second makes one set with nine references to it, and every digit would collide with every other.
Code Walkthrough
rows, cols, boxes = ...: We initialize 3 dictionaries mapping integers (0-8) to Hash Sets.for r... for c...: Iterate through all 81 cells.if v == '.': continue: Ignore empty cells.b = (r // 3) * 3 + (c // 3): Calculate the box index using the formula.if v in rows[r]...: Check our 3 "attendance sheets" (sets). If this valuevhas already been seen in the current row, column, or box, the Sudoku is invalid, so returnFalse.rows[r].add(v)...: Record that we have now seen valuevin rowr, colc, and boxb.
Trace
Let's trace cell r=4, c=7 with value '5':
b = (4 // 3) * 3 + (7 // 3) = 1 * 3 + 2 = 5. It belongs to box 5.- Check
rows[4],cols[7],boxes[5]for'5'. - Assuming it's not there, add
'5'torows[4],cols[7], andboxes[5].
Complexity
O(1) time and space. The board is always 81 cells. Both loops run exactly nine times, so the work is bounded by a constant.
Calling this O(n^2) is the mistake the problem is testing for. Adding "and O(n^4) for a general n^2 \times n^2 board" is a good second sentence, but the first answer should be the true one.
Time Complexity: The board is always fixed at 9x9, so we always visit exactly 81 cells. For each cell, calculating the box index takes O(1) math operations, and looking up/inserting into the 3 hash sets takes O(1). Total time is bounded by 81 \times O(1) = O(1). If parameterized by n (where grid is n \times n), it's O(n^2). Space Complexity: There are 27 sets in total (9 rows, 9 cols, 9 boxes). Each set can hold at most 9 digits. The total maximum number of items stored is 27 \times 9 = 243. Since this is strictly bounded by a constant, the space complexity is O(1). Parameterized by n, it's O(n^2) space for the hash sets.
The bitmask version
Twenty-seven Set objects is heavy machinery for 27 groups of 9 digits. Since there are only nine digits, one group's entire state fits in a single 9-bit integer, where bit d means "digit d seen".
python
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
...
bit = 1 << d # one bit at position d
if rows[r] & bit or cols[c] & bit or boxes[b] & bit: # membership test
return False
rows[r] |= bit # insert& keeps bits set in both operands, so a non-zero result means the digit is already there. |= turns the bit on and leaves the rest alone. Twenty-seven integers replace the whole structure, with no hashing and no allocation.
It makes no visible difference on 81 cells. It matters enormously in a Sudoku solver, which runs this check millions of times. 4.29 builds the vocabulary.
Edge cases
An empty board is valid. A valid but unsolvable board is still valid. The input that tests your box formula is two equal digits in the same box but different rows and columns, such as a 5 at (0,0) and a 5 at (1,1).
Where this goes next
- Sudoku Solver — this check becomes the pruning test inside a backtracking search. The check is fast and the search is slow, which is why the bitmask earns its keep there. Chapter 4.18.
- N-Queens — the same "name the group" idea on different geometry. Two queens share a
↘diagonal whenr - cmatches, and a↗diagonal whenr + cmatches. Sor - candr + care the group names, exactly as(r//3)*3 + c//3is here. Chapter 4.18. - Grid problems generally — keying a visited set by
r * cols + cinstead of a tuple is faster, and it sidesteps the JavaScript problem that an array cannot be aSetkey by value. Chapter 4.20.
The rule: when an item belongs to several overlapping groups, give each group a computable name and keep one seen-set per group.
What the interviewer will push on
"Time complexity?" O(1). This is asked here specifically to see whether you notice.
"Derive the box index." Talk through r // 3 and c // 3, then the multiply-and-add, then check it on (3,2).
"Less memory?" The bitmask.
"Does this check solvability?" No. If they then ask for solvability, that is backtracking, and general n×n Sudoku is NP-complete.
"Extend it to a 16×16 board." Boxes become 4×4, so the formula becomes (r // 4) * 4 + (c // 4) and the mask needs 16 bits. Answering with the general formula shows you understood it rather than memorised it.
One thing to volunteer: say that all three checks are one operation on differently-named groups. That framing is what makes the code obvious and what carries over to N-Queens.
Next: 4.4.9 Longest Consecutive Sequence — the one problem here where proving the complexity is harder than writing the code.