Valid Sudoku

ARRAYS & HASHING · MEDIUM

The problem

You’re given a 9×9 Sudoku board that’s only partially filled in — each cell holds either a digit '1'-'9' or a '.' standing in for “not filled in yet.” Your job is not to solve the puzzle — there’s no reasoning about which digits could legally go where. It’s only to check whether the digits already placed break any of Sudoku’s three rules: no repeated digit within any single row, no repeated digit within any single column, and no repeated digit within any of the nine non-overlapping 3×3 boxes. An empty cell imposes no constraint on anything — only actual placed digits can conflict with each other. Return true if the board as it stands right now is consistent with all three rules, false the moment any one of them is broken.

Solution 1: Brute force — compare every filled cell against every other

Read the rules literally: collect every filled cell, then for every pair of them, ask “do these two share a row, a column, or a box, and do they hold the same digit?” If any pair answers yes to both, the board is invalid. This is honest and correct — it directly checks the definition of a conflict — but it’s wasteful: it doesn’t stop at the natural per-row/per-column/per-box boundaries the problem actually has, it re-derives which box each cell belongs to from scratch for every single pair, and it spends a full comparison on pairs that don’t even share a unit, only to discover that fact after the fact.

function boxIndex(r, c) {
  return Math.floor(r / 3) * 3 + Math.floor(c / 3);
}

function sameUnit(r1, c1, r2, c2) {
  if (r1 === r2) return true;
  if (c1 === c2) return true;
  return boxIndex(r1, c1) === boxIndex(r2, c2);
}

function isValidSudokuBrute(board) {
  const cells = [];
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== '.') cells.push([r, c, board[r][c]]);
    }
  }

  for (let i = 0; i < cells.length; i++) {
    for (let j = i + 1; j < cells.length; j++) {
      const [r1, c1, v1] = cells[i];
      const [r2, c2, v2] = cells[j];
      if (v1 === v2 && sameUnit(r1, c1, r2, c2)) return false;
    }
  }
  return true;
}

Line by line:

cells collects only the filled positions — up to 81 of them, but usually far fewer — each remembered as [row, col, digit].
boxIndex rounds a cell’s row and column down to its box’s top-left corner: Math.floor(r / 3) gives which of the 3 “box rows” (0, 1, or 2) the cell is in, * 3 converts that to a box-row offset, and Math.floor(c / 3) adds which of the 3 “box columns” it’s in — together, a number 0-8 identifying one of the nine 3×3 boxes.
sameUnit checks all three ways two cells can be forced to share a Sudoku rule: same row, same column, or same box (checked last, since it’s the most expensive of the three).
The nested loop (j = i + 1, not j = 0) checks each pair exactly once — comparing i to j is the same check as j to i, so trying both directions would be redundant.
v1 === v2 && sameUnit(...) — both conditions must hold for a real conflict. Matching digits alone are fine anywhere on the board; sharing a unit alone is fine as long as the digits differ.

Interactive visualization

cell i in the current pair cell j in the current pair conflict found — breaks validity

9×9 board with 6 digits placed — brute force pairwise comparison

Press Play or Step to begin.

Step 0 / 0

Complexity: O(n⁴) in the general case — up to n² filled cells, every pair of them compared.

Solution 2: Optimal — one pass, three hash trackers

The insight: a “conflict” is really just “have I already placed this digit in this row / this column / this box?” — a membership question, and hash sets answer membership questions in O(1). Walk the board once, and for every filled cell, check three small sets: has this digit already been seen in this row? This column? This box (found via the same boxIndex formula as above)? If any of the three say yes, the board is invalid — stop immediately. Otherwise, record the digit in all three trackers and move on. No pair of cells is ever explicitly compared against each other — the trackers do that work implicitly, one cell at a time.

function isValidSudoku(board) {
  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 val = board[r][c];
      if (val === '.') continue;

      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if (rows[r].has(val) || cols[c].has(val) || boxes[b].has(val)) {
        return false;
      }

      rows[r].add(val);
      cols[c].add(val);
      boxes[b].add(val);
    }
  }
  return true;
}

Line by line:

rows, cols, and boxes are 9 independent Sets each — 27 trackers total, one per row, one per column, one per box. Independent because knowing a digit repeats in a row tells you nothing about whether it repeats in a column or box; the three groupings of cells only overlap at individual cells.
if (val === '.') continue — empty cells are skipped entirely, exactly as the problem specifies: they impose no constraint.
b reuses the same box-index formula as the brute-force solution.
rows[r].has(val) || cols[c].has(val) || boxes[b].has(val) — the instant any one of the three trackers already contains this digit, the board is provably invalid; || short-circuits, so at most one Set.has lookup (O(1)) beyond the first true is ever wasted.
Only after surviving all three checks does the digit get added to all three trackers — a digit is never recorded as “seen” until it’s confirmed not to conflict with anything seen so far.

Interactive visualization

cell currently being checked earlier cell that already holds this digit confirmed clean — no conflict yet conflict found — breaks validity

Same board, same conflict — watch how few single-cell checks it takes

Press Play or Step to begin.

Step 0 / 0

Complexity: O(n²) — every cell visited once, O(1) tracker lookups per cell.

Complexity comparison

Solution	Time	Space
Brute force (pairwise comparison)	O(n⁴) general case	O(n²)
Optimal (row/column/box hash trackers)	O(n²)	O(n²)

Because n is fixed at 9, both solutions are technically O(1) — bounded work on a bounded board, the most honest version of that caveat anywhere on this site. But framed the way this site’s other pages reason about the general n×n case, the gap is real, not invented: brute force collects up to n² filled cells and compares every pair of them, so its work scales like O((n²)²) = O(n⁴) as the board size grows. The optimal pass touches each of the n² cells exactly once with O(1) tracker lookups, so its work scales like O(n²) — a genuine two-power gap in that general framing. On the actual fixed 9×9 board, though, both collapse to small constants — at most 81×80÷2 = 3,240 pairwise comparisons for brute force versus at most 81 single-cell checks for optimal. The demo above shows exactly that in miniature: 13 pairwise comparisons versus 5 single-cell checks to catch the identical conflict. That’s “much more comparison work for the same fixed board size,” not an asymptotic blowup that keeps growing — because on this problem, the input never gets bigger than 9×9.

Interview corner

The problem says “validate,” not “solve” — why doesn’t either solution ever need to try placing a digit into an empty cell?

Validating only asks whether the digits already on the board violate a rule — empty cells contribute zero information either way, so both solutions simply skip '.' and move on.
Actually solving a Sudoku (LeetCode’s separate, much harder “Sudoku Solver” problem) requires trying hypothetical digits in every empty cell and backtracking when a choice doesn’t pan out — a search over an exponential space of possibilities.
Because Valid Sudoku makes no choices and searches nothing, both solutions here run in bounded time on a fixed board — there’s no tree of guesses to explore, only facts to check.

A cell’s row and column together already pin down exactly where it is — so why isn’t checking its box redundant with the row and column checks?

Knowing a cell’s row and column tells you where that one cell is — it doesn’t tell you which other cells it’s forbidden from repeating a digit with.
Row membership groups one set of 9 cells; column membership groups a different set of 9 cells; box membership groups yet a third set of 9 cells. The three groupings overlap only at individual cells — none is derivable from the other two.
Concretely: (0,0) and (2,2) share neither a row nor a column, but they do share box 0 — a rule only the box check catches (this exact pair shows up as Pair 3 in Solution 1’s demo above).

Both solutions only ever read from the board and never write to it — why does that matter for how they scale?

The question is a yes/no check on the board’s current state — every filled cell is a fixed fact, not a guess that might later need to be undone.
Because there’s nothing to mutate or backtrack, the extra space either solution needs scales only with the board’s own size (a filled-cell list, or 27 small hash sets) — never with a search tree.
That’s the same line that separates this problem from “Sudoku Solver”: the moment you need to place a digit and possibly take it back, you need backtracking state on top of everything here.
↳ Common follow-up: “How would you adapt this to also solve the board?” You’d keep these same three trackers (they’re exactly what a backtracking solver needs to check “is this digit safe to place here?” in O(1)) and add a recursive search over empty cells that adds a digit, recurses, and removes it again on failure.

Trick question — what does this log?

const seen = {};
seen[5] = true;
console.log(seen['5']);

const seenSet = new Set();
seenSet.add(5);
console.log(seenSet.has('5'));

Answer: true, then false — same digit, opposite results, depending only on which data structure is holding it.
Plain object keys are always coerced to strings, so seen[5] and seen['5'] write and read the exact same property — the number 5 and the string '5' are indistinguishable as object keys.
Set uses SameValueZero equality instead, which does distinguish types — 5 and '5' are two different members of a Set, so seenSet.has('5') is false even though seenSet.has(5) is true.
⚠ Trap: this problem’s board holds digits as strings ('5', not 5) — LeetCode’s own input format. Solution 2 above works correctly only because it consistently stores and looks up that same string value in every Set. Silently normalizing a value to a Number in just one spot (say, while generating a test board) would make a real duplicate invisible to a Set-based tracker — while a plain-object-based tracker would happen to paper over the exact same mistake, coercing both back to the same key. Consistency of type, not which structure you pick, is what actually matters here.

Quiz

1. Why does the optimal solution need THREE separate groups of trackers (row, column, and box), instead of one shared ‘seen digits’ tracker?

Row, column, and box are three independent groupings of cells — a conflict in one tells you nothing about the other two
One shared tracker would work identically — splitting into three is purely a readability choice
Box tracking is redundant, since a cell’s row and column already determine its box

2. In Solution 1’s pairwise check, why does a conflict require BOTH matching digits AND a shared unit — not just matching digits?

A repeated digit is only a violation within the same row, column, or box — anywhere else, repeats are perfectly legal
Matching digits are always invalid, no matter where the two cells are on the board
Sharing a unit is enough on its own — the actual digit values don’t matter

3. What does Math.floor(r / 3) * 3 + Math.floor(c / 3) compute for a cell at (r, c)?

The 0-8 index of the 3×3 box that cell belongs to
A re-derivation of the cell’s own row index, unrelated to boxes
An arbitrary hash used only to randomize iteration order

4. The board is a fixed 9×9 grid — so why is it still meaningful to say brute force is ‘O(n⁴)’ and optimal is ‘O(n²)’?

Reasoned about as the general n×n case, brute force’s pairwise work genuinely scales like n⁴ while optimal’s single pass scales like n² — even though both are O(1) on this specific fixed board
It’s a fabricated distinction — both are exactly O(1) and there’s no honest way to compare them
It reflects actual measured runtime differences of many seconds on a real 9×9 board

5. Why can both solutions return false the INSTANT they find one conflict, without finishing the rest of the scan?

One confirmed conflict is enough to make the whole board invalid, permanently — nothing checked afterward could change that
They can’t actually stop early — the working code always inspects all 81 cells regardless
Stopping early only happens to work for THIS demo board, not in general