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.

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.

• Row group of cell (r, c): just r.
• 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.

Integer division picks the box; multiply-and-add flattens the pair into one number.

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 True

TypeScript

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.

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.

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".

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 when r - c matches, and a ↗ diagonal when r + c matches. So r - c and r + c are the group names, exactly as (r//3)*3 + c//3 is here. Chapter 4.18.
• Grid problems generally — keying a visited set by r * cols + c instead of a tuple is faster, and it sidesteps the JavaScript problem that an array cannot be a Set key 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.