Valid Sudoku - One Pass, Three Memberships

You’ve used a hash set for membership (Day 4), frequency (Day 5), and sequence heads (Day 26). Valid Sudoku is the Arrays & Hashing closer that glues them into a grid: for every filled cell, three “have I seen digit d here already?” checks. Empty cells (’.’) are free passes - this problem only validates the filled partial board, not “does a solution exist?”

The problem

Determine if a 9×9 board is valid. Only filled cells matter. A board is valid if:

• Each row contains digits 1-9 at most once
• Each column contains digits 1-9 at most once
• Each of the nine 3×3 boxes contains digits 1-9 at most once

It does not need to be solvable. Two 8s in the same box → invalid, even if every other cell is empty.

// Partial valid board (LeetCode example shape)
// Top-left box has 5,3,6,9,8 - all unique → OK
// Change board[0][0] from '5' to '8' → two 8s in that box → false

The box index - the only “trick”

Rows and columns are obvious: index r and c. Boxes need a single id from 0-8:

const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
// r=0..2,c=0..2 → 0 | r=0..2,c=3..5 → 1 | … | r=6..8,c=6..8 → 8

Draw the nine boxes once. After that, every cell maps to one box set the same way.

Diagram: same digit can collide on a row, a column, or a 3×3 box - three membership checks.

Approach 1: Brute - re-scan row, col, box per cell

For every filled cell, walk the rest of its row, column, and box looking for the same digit. Correct. On a fixed 9×9 it is still O(1) work per board - just a larger constant (nested loops over 9).

function isValidBrute(board) {
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      if (v === '.') continue;
      for (let k = c + 1; k < 9; k++) if (board[r][k] === v) return false;
      for (let k = r + 1; k < 9; k++) if (board[k][c] === v) return false;
      const br = Math.floor(r / 3) * 3, bc = Math.floor(c / 3) * 3;
      for (let i = br; i < br + 3; i++) {
        for (let j = bc; j < bc + 3; j++) {
          if (i === r && j === c) continue;
          if (board[i][j] === v) return false;
        }
      }
    }
  }
  return true;
}

Approach 2: Sets - one pass, three memberships (interview pattern)

Allocate 9 sets for rows, 9 for columns, 9 for boxes. Visit each cell once. If the digit is already in that row/col/box set → invalid. Otherwise add it.

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

This is the answer you want on a whiteboard: clear invariant, one pass, O(1) membership. Same mental model as Day 4’s “seen?” set - just three dimensions.

Approach 3: Bitmasks - same idea, integers

Digits 1-9 fit in 9 bits. Keep three Uint16Array(9) masks. Test-and-set a bit instead of Set.has/add.

function isValidBitmask(board) {
  const rows = new Uint16Array(9);
  const cols = new Uint16Array(9);
  const boxes = new Uint16Array(9);
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const ch = board[r][c];
      if (ch === '.') continue;
      const bit = 1 << (ch.charCodeAt(0) - 49); // '1' → bit 0
      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;
}

Benchmark - fixed size, constant factors (Node, 30-run median)

Batch of 20,000 boards (~75% filled). Headline is correctness agreement + which constant wins - not “O(n) vs O(n²)” (there is no growing n).

Approach	Median ms / 20,000 boards	vs bitmask
Brute re-scan	48.102	2.99× slower
Array of Sets (interview pattern)	251.538	15.65× slower
Bitmasks	16.074	1.0× (fastest)

Bitmask is ~2.99× faster than brute. Sets are ~5.23× slower than brute on this host - allocating 27 tiny Sets per board taxes a problem whose entire state fits in a few integers. Same honesty family as Day 18 (bucket sort lost to sort in practice) and Day 26 (dense 100K sort ≈ set).

Product claim for interviews: ship the Set pattern for clarity; know bitmasks if they ask about constants. Do not claim “Sets are always faster.”

What breaks?

• Validating only rows and columns - the classic miss. Two 8s can sit in different rows/cols but the same box (LeetCode invalid example).
• Wrong box formula - r % 3 alone is not enough; you need band + stack: floor(r/3)*3 + floor(c/3).
• Treating empty as a digit - ’.’ must skip; otherwise every empty collides with every empty.
• Solving instead of validating - this is not Day “Sudoku Solver.” Partial boards with a unique completion path can still be “valid” with many empties.
• Selling Sets as free speed - on fixed 9×9, allocation can lose to a tight brute scan. Pattern ≠ wall-clock win.

How it connects

• Day 4 (Contains Duplicate): same “seen this key?” set. Here the key is scoped to a row, col, or box.
• Day 5 / Day 12 (frequency / group): digits are categories; collision = count would exceed 1.
• Day 18 (Top K): Big-O honesty - textbook structure can lose on constants.
• Day 26 (sequence heads): one O(1) membership check decides control flow.
• Day 29 / Day 31 (CHECK / EXCLUDE): multi-axis integrity - a value can be fine alone and illegal in combination with peers (row + col + box are three constraints, like multi-row rules).

Quiz