Valid Sudoku

The problem

Determine if a 9 × 9 Sudoku board is valid. Only filled cells ('1'–'9') are checked; '.' is empty. It need not be solvable — only no conflicts in rows, columns, or 3×3 boxes.

A valid partial board returns true; duplicate 5 in a row returns false.

Brute force

For each cell, scan its row, column, and box for duplicates. Redundant work but O(1) board size so O(1) practically O(81·9).

Optimal: one pass with three set groups

function isValidSudoku(board: string[][]): boolean {
  const rows: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const cols: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const boxes: Set<string>[] = Array.from({ length: 9 }, () => new Set());

  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;
}

Bitmasks (9 bits each) are a tight alternative:

function isValidSudokuBits(board: string[][]): boolean {
  const rows = Array(9).fill(0);
  const cols = Array(9).fill(0);
  const boxes = Array(9).fill(0);

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] === ".") continue;
      const bit = 1 << (board[r][c].charCodeAt(0) - 49);
      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if (rows[r] & bit || cols[c] & bit || boxes[b] & bit) return false;
      rows[r] |= bit;
      cols[c] |= bit;
      boxes[b] |= bit;
    }
  }
  return true;
}

Time	O(1) for fixed 9×9 (O(n²) if generalized)
Space	O(1)

Edge cases

• Completely empty → true
• Only one filled cell → true
• Conflict only in a box, not row/col
• Digit '0' not used

Common bugs

• Wrong box index formula
• Validating solvability instead of partial validity
• Forgetting boxes entirely

Interview delivery

1. Three constraints.
2. One scan.
3. Box index r/3*3 + c/3.
4. Not a full solver (that’s backtracking).
5. O(1) board.

Related

• N-Queens
• Set Matrix Zeroes
• Spiral Matrix
• Word Search

Box index derivation

Boxes numbered 0..8 left-to-right, top-to-bottom:

box = Math.floor(r / 3) * 3 + Math.floor(c / 3)

Examples: (0,0)→0, (0,4)→1, (4,4)→4, (8,8)→8. Write one example when coding.

Valid ≠ solvable

A board can be valid (no conflicts) yet unsolvable due to global constraints. This problem does not require a solver. Solving is backtracking (N-Queens cousin).

Encoding tricks

Strings like "r0-5", "c3-5", "b1-5" in one Set also work — one collection, three encoded keys per digit. Slightly slower constants, compact code.

Further reading

• LeetCode 36 — Valid Sudoku
• Sudoku