ASAPUtils
The signal
Three independent “no duplicates in this collection” checks, running simultaneously. Duplicate detection is a hash set; the only thing that makes this problem more than trivial is figuring out how to identify which box a cell belongs to.
Note the constraints carefully: the board is always 9×9. Nothing scales, so this is O(1) work by definition — a rare and worth-stating observation.
Approach ladder
1. Three separate passes
Check all rows, then all columns, then all boxes. Perfectly correct, three times the code, and it walks the board three times.
2. What is it wasting?
Every cell already knows its row, its column, and its box. Each cell only needs to be visited once if you can update all three checks at that moment.
3. The box index
The one piece of real thinking. A cell at (r, c) is in box:
boxIndex = (r / 3) * 3 + (c / 3) // integer division
Why: r / 3 collapses rows 0–2 → band 0, 3–5 → band 1, 6–8 → band 2. Same for columns. Multiplying
the row band by 3 spreads the nine (band, band) combinations across 0–8 without collisions. Write
out (0,0) → 0, (0,8) → 2, (4,4) → 4, (8,8) → 8 by hand once and it stops being magic.
4. Optimal — one pass, 27 sets
bool isValidSudoku(vector<vector<char>>& b) {
vector<unordered_set<char>> rows(9), cols(9), boxes(9);
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
char v = b[r][c];
if (v == '.') continue;
int box = (r / 3) * 3 + (c / 3);
if (rows[r].count(v) || cols[c].count(v) || boxes[box].count(v))
return false;
rows[r].insert(v);
cols[c].insert(v);
boxes[box].insert(v);
}
return true;
}
function isValidSudoku(b) {
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 v = b[r][c];
if (v === '.') continue;
const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
if (rows[r].has(v) || cols[c].has(v) || boxes[box].has(v)) return false;
rows[r].add(v); cols[c].add(v); boxes[box].add(v);
}
return true;
}
Complexity
- Time O(1) — 81 cells, always. (O(n²) if you generalise to an n×n board.)
- Space O(1) — 27 sets of at most 9 entries.
Traps
Math.floorin JavaScript.r / 3gives1.333…, so the box index silently becomes a float and every lookup misses. C++ integer division does this for you; JS does not.- Not skipping
'.'. Empty cells would instantly look like duplicates of each other. Array(9).fill(new Set()). That’s one set referenced nine times, so every row shares state and everything fails. UseArray.from({length: 9}, () => new Set()).- Checking after inserting. Then every cell collides with itself.
Blank re-solve prompt
Validate a 9×9 Sudoku board in a single pass over the cells. Derive the box index formula from scratch — don’t recall it.