Skip to main content

43. Valid Sudoku

mediumAsked at Ola

Determine if a partially-filled 9x9 Sudoku board is valid.

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

Problem

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated against the rules: each row, column, and 3x3 sub-box must contain digits 1-9 without repetition.

Constraints

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

Examples

Example 1

Input
9x9 board with sample digits
Output
true

Example 2

Input
Board with two 8s in first column
Output
false

Approaches

1. Three-pass scan

Separately validate rows, columns, and boxes with a set each pass.

Time
O(81)
Space
O(9)
// 3 nested loops, set per row/col/box, omitted for brevity

Tradeoff:

2. Single pass with composite keys

One scan; for each digit add three keys ('row', 'col', 'box') to a set, rejecting collisions.

Time
O(81)
Space
O(81)
function isValidSudoku(board) {
  const seen = 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)}-${Math.floor(c/3)}`;
      const keys = [`r${r}#${v}`, `c${c}#${v}`, `b${b}#${v}`];
      for (const k of keys) {
        if (seen.has(k)) return false;
        seen.add(k);
      }
    }
  }
  return true;
}

Tradeoff:

Ola-specific tips

Ola interviewers like the single-pass composite-key pattern; tie it to validating that no city zone label appears in two unrelated dispatch buckets.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →