Skip to main content

43. Valid Sudoku

mediumAsked at Reddit

Determine if a 9x9 Sudoku board configuration is valid. Reddit uses this to test multi-key hash-set technique — the same shape used when validating that a moderator action is consistent across multiple constraint sets (subreddit + user + action).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, occasional medium.

Problem

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: each row must contain the digits 1-9 without repetition; each column must contain the digits 1-9 without repetition; each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'.

Examples

Example 1

Input
board = [valid 9x9 partial Sudoku]
Output
true

Example 2

Input
board = [same board but with two 8s in column 1]
Output
false

Approaches

1. Three passes (rows, cols, boxes)

Walk each row checking duplicates. Walk each col. Walk each 3x3 box.

Time
O(81 * 3)
Space
O(9)
function isValidSudoku(board) {
  for (let i = 0; i < 9; i++) {
    const row = new Set(), col = new Set(), box = new Set();
    for (let j = 0; j < 9; j++) {
      if (board[i][j] !== '.' && row.has(board[i][j])) return false;
      if (board[i][j] !== '.') row.add(board[i][j]);
      if (board[j][i] !== '.' && col.has(board[j][i])) return false;
      if (board[j][i] !== '.') col.add(board[j][i]);
      const r = 3 * Math.floor(i / 3) + Math.floor(j / 3);
      const c = 3 * (i % 3) + (j % 3);
      if (board[r][c] !== '.' && box.has(board[r][c])) return false;
      if (board[r][c] !== '.') box.add(board[r][c]);
    }
  }
  return true;
}

Tradeoff: Works. The 3x3 box indexing is clever but error-prone.

2. Single pass with composite keys (optimal)

One set containing keys like '5 in row 2', '5 in col 7', '5 in box 1'. Insert and check in one pass.

Time
O(81)
Space
O(9*9*3)
function isValidSudoku(board) {
  const seen = new Set();
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const v = board[i][j];
      if (v === '.') continue;
      const r = `r${i}-${v}`, c = `c${j}-${v}`, b = `b${Math.floor(i/3)}${Math.floor(j/3)}-${v}`;
      if (seen.has(r) || seen.has(c) || seen.has(b)) return false;
      seen.add(r); seen.add(c); seen.add(b);
    }
  }
  return true;
}

Tradeoff: Single pass. Composite-key trick generalizes well to multi-dimensional constraint checks.

Reddit-specific tips

Reddit interviewers prefer the composite-key approach because it's the most extensible — drop in another constraint axis (diagonal, color-grouping) without touching the loop. Bonus signal: connect to multi-constraint validation in their moderation pipeline.

Common mistakes

  • Forgetting to skip '.' cells (they don't count as repeats).
  • Mis-computing the 3x3 box index.
  • Using a 2D array of sets (works but uglier than composite keys).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Solve Sudoku (LC 37) — backtracking on top of validation.
  • What if the board is 16x16?
  • How would you verify in parallel?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why composite keys instead of three arrays of sets?

Single data structure is easier to reason about and extends to N constraints with no new code.

What about partial boards?

The problem accepts '.' for unfilled cells — we just skip them.

Practice these live with InterviewChamp.AI

Drill Valid Sudoku and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →