Given a partially filled 9 x 9 Sudoku board, determine whether the currently placed digits are valid. The board uses the strings "1"–"9" for digits and "." for empty cells.
The board is valid when:
- each row contains no repeated digit,
- each column contains no repeated digit,
- each of the nine 3 x 3 sub-boxes contains no repeated digit.
Only the filled cells are checked — the board does not need to be solvable. Return true if valid, false otherwise.
Example
No row, column, or 3x3 box repeats a digit.
Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit "1"-"9" or ".".
Intuition
The rules are three independent checks, so the plainest approach runs three sweeps. For each of the nine rows collect its filled digits and look for a repeat; do the same for each column; then for each of the nine 3 x 3 boxes. If any group repeats a digit the board is invalid.
function isValidSudoku(board) {
// True if a group of cells repeats any digit (ignoring '.').
const hasDup = (cells) => {
const seen = new Set();
for (const d of cells) {
if (d === '.') continue; // empty cells never conflict
if (seen.has(d)) return true; // digit already in this group
seen.add(d);
}
return false;
};
// Pass 1: every row.
for (let r = 0; r < 9; r++) {
if (hasDup(board[r])) return false;
}
// Pass 2: every column (gather the 9 cells down each column).
for (let c = 0; c < 9; c++) {
const col = [];
for (let r = 0; r < 9; r++) col.push(board[r][c]);
if (hasDup(col)) return false;
}
// Pass 3: every 3x3 box (top-left corners at multiples of 3).
for (let br = 0; br < 9; br += 3) {
for (let bc = 0; bc < 9; bc += 3) {
const box = [];
for (let r = br; r < br + 3; r++)
for (let c = bc; c < bc + 3; c++) box.push(board[r][c]);
if (hasDup(box)) return false;
}
}
return true;
}That works, but it walks the board three separate times and re-derives a fresh Set for every group. Can we do it in one pass and keep it cleaner?
Notice the only thing each group cares about is: has this digit already appeared in my row, my column, or my box? A repeat is a duplicate-detection problem, and a hash set answers "have I seen this before?" in O(1). So we don't need to gather groups at all — we can scan the 81 cells once and, at each filled cell, test three memberships at once.
Keep three kinds of seen-marker, tagged so they can't collide: row-r-d, col-c-d, and box-b-d, where the box index b = floor(r/3) * 3 + floor(c/3) (0–8). For a digit d at (r, c), if any of its three keys is already in the set, that digit repeats in that row, column, or box — return false immediately. Otherwise add all three keys and move on. The same digit 5 is free to appear all over the board; only a matching key (same line or same box) is a conflict.
The set check is the same one-line seen.has(...) for all three rules — no special-casing per group. Here's the left-to-right, top-to-bottom scan over a board whose column 0 hides a repeated 5:
scan order: row by row, testing three keys at each filled cell
First filled cell: stamp `row-0-5`, `col-0-5`, and `box-0-5`. All three are new.
Routine: every filled cell stamps its three keys. Column 0 now holds a 5 and a 6.
A second 5 — but row 1, column 5, box 1 are all different from the first 5's groups, so no key collides. The same digit is free to repeat elsewhere.
Down column 0, this 5 matches the 5 at (0,0): `col-0-5` is already in the set. The board is invalid — stop immediately.
Optimization
Three sets of seen keys
Walk every cell once. For a filled cell, derive three keys: row r, col c, and box (floor(r/3), floor(c/3)). Keep a Set of "row-r-d", "col-c-d", "box-b-d" strings; if any key is already present the digit repeats and the board is invalid. If the full scan finds no collision the board is valid.
O(1) time and space (the board is a fixed 9x9 = 81 cells).
function isValidSudoku(board) {
// One set holds every constraint we've already committed to, tagged by kind.
const seen = new Set();
// Single pass over all 81 cells; the three rules are checked together.
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const d = board[r][c];
if (d === ".") continue; // empty cells place no constraint
// Which 3x3 box owns this cell: 0..8, row-major over the box grid.
const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
// The same digit may legally repeat across the board — only within
// the *same* row, *same* column, or *same* box is it a conflict.
const keys = ["row-" + r + "-" + d, "col-" + c + "-" + d, "box-" + box + "-" + d];
for (const key of keys) {
if (seen.has(key)) return false; // this digit already claimed that line/box
seen.add(key);
}
}
}
// Scanned every cell with no collision — the placement is valid.
return true;
}Complexity analysis
Time complexity: O(1) for this problem. Here's why:
- The board is a fixed
9 x 9, so the scan always visits exactly 81 cells. - Each cell does a constant amount of work: derive three keys and do three O(1) set probes.
There is no loop whose length grows with an input size, so the work is bounded by a constant — O(1). Phrased for a general n x n board it would be O(n²): one visit per cell over the n² cells, with O(1) per cell.
Space complexity: O(1) for this problem. Here's why:
- The
seenset holds at most three keys per filled cell, so at most 3 × 81 = 243 keys — a fixed bound. - No other storage grows with the board.
So the extra space is constant, O(1). For a general n x n board the set holds up to O(n²) keys, so it would be O(n²). Nothing is returned but a boolean, so there is no output array to count.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| board = ......... ......... ......... ......... ......... ......... ......... ......... ......... | true | Empty board — no filled cells means no constraints, so it is trivially valid. |
| board = ......... ......... ......... ......... ....9.... ......... ......... ......... ......... | true | A single filled cell can never conflict with itself. |
| board = ......... ......... 6......6. ......... ......... ......... ......... ......... ......... | false | Row conflict — two 6s in row 2 (different boxes), caught by the shared `row-2-6` key. |
| board = ...2..... ......... ......... ......... ......... ...2..... ......... ......... ......... | false | Column conflict — two 2s down column 3 (different rows and boxes). |
| board = ......... ......... ......... ...4..... ......... .....4... ......... ......... ......... | false | Box-only conflict — two 4s in the centre box at different rows and columns. |
| board = 7........ ......... ......... ......... ....7.... ......... ......... ......... ........7 | true | Same digit, distinct row/column/box each time — repeats across the board are allowed. |
Try it yourself
Write your solution against the real judge before checking the reference.