36. Valid Sudoku

Validate a partially-filled 9×9 Sudoku board without solving it. The trick is a single pass using three groups of hash sets— one per row, one per column, and one per 3×3 box — so each digit is checked and recorded in O(1) per cell.

● MediumHash SetMatrix / GridValidationTypeScript

PROBLEM What we're solving

Given a 9×9 board of digits 1–9 and '.' (empty), return trueif the board is valid — that is, no digit appears twice in any row, column, or 3×3 sub-box.

Concrete example. The top-left 3×3 sub-box contains 5, 3, 6, 9, 8 — all distinct. Row 1 is 5 3 . . 7 . . . . — again all distinct digits. The standard LeetCode example board returns true. If you instead put a second 8 in row 1, it returns false immediately.

You do notneed to solve or complete the board — only check whether what's already filled violates the rules.

KEY IDEA Three families of sets — one pass

Insight → a digit is invalid if and only if the same digit has already appeared in its row, column, or box. Maintain 9 row-sets, 9 col-sets, and 9 box-sets. For every filled cell, check all three — if the digit is already in any set, return false; otherwise add it to all three. One O(81) pass, three O(1) lookups per cell.

RECIPE Allocate sets, scan, check-then-insert

0 · Allocate. Create three arrays of 9 empty Set<string> — rows[0..8], cols[0..8], boxes[0..8]. One set per unit. This is just nine buckets per dimension.
1 · Iterate. Nested loops r 0→8, c 0→8. For each cell, skip immediately if val === '.'.
2 · Key the box. boxIdx = Math.floor(r/3)*3 + Math.floor(c/3). This maps any (r, c) to an index 0–8 uniquely identifying its 3×3 sub-grid — the key insight that avoids storing a 2D array of sets.
3 · Check, then insert. If rows[r], cols[c], or boxes[boxIdx] already has val, return false. Otherwise .add(val)to all three. Check before insert so you never mark the duplicate as "seen."
4 · Return true. Survived all 81 cells → valid board.

Classic confusion → the box index formula trips people up. The correct formula is Math.floor(r/3)*3 + Math.floor(c/3), which maps the 3×3 sub-grid coordinates to a flat index 0–8. A common mistake is using r*3+c (that gives 0–80, not 0–8) or forgetting the *3 multiplier. Write it out for cell (4,7): Math.floor(4/3)*3 + Math.floor(7/3) = 1*3+2 = 5— box 5, which is the middle-right 3×3. Correct.

COST Complexity & alternatives

Brute force (per-cell scan)

O(81²)

For each of 81 cells, rescan every row/col/box — wasteful.

Three hash-set families

O(1)

81 cells × O(1) lookup & insert = effectively constant time and space.

The board is always 9×9 so both are technically O(1) (bounded constants), but the hash-set approach is O(1) per cell vs O(81) per cell — a 81× practical improvement and the pattern that scales to arbitrary N×N Sudoku.

Alternative — bit masking: replace each Set<string> with a number bitmask (bit k set = digit k+1 seen). Same O(1) logic but avoids object allocation.

Pattern transfer → the "key a 2D region to a flat index" trick appears in Sudoku Solver (LeetCode 37), N-Queens (diagonal hashing), and any problem where you partition a grid into tiles and need O(1) membership per tile. The check-then-insert pattern is also identical to the hash-set deduplication step in Contains Duplicate and Longest Consecutive Sequence.

RUN IT Scan once — three hash sets catch every duplicate

Board (9 rows, . for empty):

step 0 / 82

STARTBoard loaded. We scan every cell once; for each digit we check row, col, and 3×3 box sets.

1▶function isValidSudoku(board: string[][]): boolean {
2▶  const rows = Array.from({ length: 9 }, () => new Set<string>());
3▶  const cols = Array.from({ length: 9 }, () => new Set<string>());
4▶  const boxes = Array.from({ length: 9 }, () => new Set<string>());
5 
6  for (let r = 0; r < 9; r++) {
7    for (let c = 0; c < 9; c++) {
8      const val = board[r][c];
9      if (val === '.') continue;
10 
11      const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);
12 
13      if (rows[r].has(val) || cols[c].has(val) || boxes[boxIdx].has(val)) {
14        return false;
15      }
16 
17      rows[r].add(val);
18      cols[c].add(val);
19      boxes[boxIdx].add(val);
20    }
21  }
22  return true;
23}

State
r: —
c: —
boxIdx: —
val: —
rows[]: 9 × ∅
cols[]: 9 × ∅
boxes[]: 9 × ∅

current cell (valid)empty cell (skipped)duplicate detectedall valid

slowfast

TYPESCRIPT The solution, annotated

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

      const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);

      if (rows[r].has(val) || cols[c].has(val) || boxes[boxIdx].has(val)) {
        return false;
      }

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

Reading it block by block

Lines 2–4 — allocate three set families. Array.from({ length: 9 }, () => new Set())creates nine independent sets for rows, nine for columns, and nine for 3×3 boxes. This is the only setup; the rest is a single scan.

Lines 6–7 — nested loop over all 81 cells. r is the row index (0–8), c is the column index (0–8). Every cell is visited exactly once.

Line 8 — skip empty cells.Dots represent unfilled squares and carry no constraint — skip immediately so they don't pollute the sets.

Line 10 — compute box index. Math.floor(r/3)*3 + Math.floor(c/3) maps any (r, c) to one of nine sub-grid indices 0–8. This is the load-bearing formula — memorize it.

Lines 12–14 — check for duplicates. A single || expression tests all three sets simultaneously. If the digit already exists in any of them, the board is invalid and we return false immediately — no need to finish scanning.

Lines 16–18 — insert into all three sets.The digit is fresh, so record it in the row's set, the column's set, and the box's set. Future cells in the same row/col/box will see it on their membership check.

Line 21 — return true.Every filled cell passed all three checks. The board obeys Sudoku rules for what's currently filled.

Complexity → O(81) = O(1) time (fixed 9×9 board — 81 cells × three O(1) set operations each). O(81) = O(1) space for the 27 sets — at most 9 elements each. For an N×N generalization it would be O(N²) time and O(N²) space.

INTERVIEWFollow-ups they'll ask

"Now solve it (LeetCode 37)?" Backtracking: pick the first empty cell, try digits 1–9 (skip any already in the row/col/box sets), recurse, undo if stuck. The same three set families from this problem serve as the fast constraint check.
"Can you do it with bit manipulation instead of sets?" Replace each Set<string> with a number bitmask. Bit k = digit k+1 seen. Check with mask & (1 << digit); insert with mask |= (1 << digit). Same O(1) logic, zero object allocation.
"What if the board is N×N?" The box key becomes Math.floor(r/k)*k + Math.floor(c/k)where k = √N. Sets become O(N) in size; overall O(N²) time and space.
"Edge cases?" A board with all dots is valid. A board with a single digit repeated in one row fails on the second occurrence. The solution handles both naturally because empty cells are skipped and the first occurrence is inserted before any check fires.
"Why check before insert, not after?"If you insert first, the first occurrence and a would-be duplicate both live in the set simultaneously — you'd need to compare set sizes, which is more complex. Check-then-insert means the set contains only "already seen" values at every membership test.

OPTIMAL Hash Set

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

      const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);

      if (rows[r].has(val) || cols[c].has(val) || boxes[boxIdx].has(val)) {
        return false;
      }

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

ALT 1 Brute force — re-scan each of the 27 units

O(1) time (fixed 9×9 board) · O(1) space

Check every row, every column, and every 3×3 box independently: for each of the 27 units, collect its non-dot digits and look for a duplicate with a nested comparison — no persistent hash sets carried across the board.

approach-2.ts
function isValidSudoku(board: string[][]): boolean {
  // Returns true if the nine cells given by (r, c) pairs have no repeated digit.
  function unitOk(cells: [number, number][]): boolean {
    const seen: string[] = [];
    for (const [r, c] of cells) {
      const val = board[r][c];
      if (val === '.') continue;
      // Linear scan against everything seen so far in THIS unit.
      for (const prev of seen) {
        if (prev === val) return false;
      }
      seen.push(val);
    }
    return true;
  }

  for (let i = 0; i < 9; i++) {
    // Row i, then column i.
    const row: [number, number][] = [];
    const col: [number, number][] = [];
    for (let k = 0; k < 9; k++) {
      row.push([i, k]);
      col.push([k, i]);
    }
    if (!unitOk(row) || !unitOk(col)) return false;
  }

  // Each of the nine 3×3 boxes.
  for (let br = 0; br < 9; br += 3) {
    for (let bc = 0; bc < 9; bc += 3) {
      const box: [number, number][] = [];
      for (let dr = 0; dr < 3; dr++) {
        for (let dc = 0; dc < 3; dc++) {
          box.push([br + dr, bc + dc]);
        }
      }
      if (!unitOk(box)) return false;
    }
  }

  return true;
}

Note → Logically identical, but it walks the board three separate times (rows, columns, boxes) and re-derives each unit's digits from scratch with an inner linear-scan dedupe. Because the board is fixed at 9×9 it's still constant work, just with a larger constant factor — the single-pass hash-set version settles each cell exactly once by computing its box index on the fly.

MNEMONIC The one-liner

"Three families of nine sets — row, col, box — check before you add."

TRIGGERS When you see _ → reach for _

"validate a grid without solving it"	hash sets per row/col/sub-grid
map (r, c) to a 3×3 region	Math.floor(r/3)*3 + Math.floor(c/3)
"detect duplicates in 2D partitions"	flat-indexed set families
"Sudoku Solver / backtracking on board"	reuse these three set families as constraints

SKELETON The reusable shape

skeleton.ts
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 val = board[r][c];
    if (val === '.') continue;
    const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);
    if (rows[r].has(val) || cols[c].has(val) || boxes[boxIdx].has(val)) return false;
    rows[r].add(val); cols[c].add(val); boxes[boxIdx].add(val);
  }
}
return true;

FLASHCARDS Tap to flip

How many sets does the solution maintain, and why?

27 sets: 9 for rows, 9 for columns, 9 for boxes. One set per "unit" — the three rule dimensions of Sudoku.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the box index for cell (r=4, c=7)?

QUESTION 02

Why are empty cells (".") skipped?

QUESTION 03

How many sets does the optimal solution maintain in total?

QUESTION 04

What is the time complexity of this algorithm?

QUESTION 05

The board has '8' in row 5 at column 2 and again at column 7. When does the algorithm return false?

QUESTION 06

A board of all "." (81 empty cells) should return:

QUESTION 07

Why must you check membership BEFORE inserting into the sets?

QUESTION 08

#36 · Valid SudokuValidate a 9×9 Sudoku board in one pass by checking each digit against three sets — its row, its column, and its 3×3 box — using the box key ⌊r/3⌋×3+⌊c/3⌋.Which algorithmic approach does this primarily use?

QUESTION 09

#36 · Valid SudokuValidate a 9×9 Sudoku board in one pass by checking each digit against three sets — its row, its column, and its 3×3 box — using the box key ⌊r/3⌋×3+⌊c/3⌋.Which implementation correctly solves it?

PROBLEM What we're solving

KEY IDEA Three families of sets — one pass

RECIPE Allocate sets, scan, check-then-insert

COST Complexity & alternatives

RUN IT Scan once — three hash sets catch every duplicate

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Hash Set

ALT 1 Brute force — re-scan each of the 27 units

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _