Skip to main content

43. Valid Sudoku

mediumAsked at Datadog

Validate a 9x9 Sudoku board against the row/col/box rules in a single pass. Datadog asks this because the constraint-encoding trick (one Set per row/col/box) is the same shape as validating multi-dimensional metric tags in a single ingestion pass.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite constraint-checking question.

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.

Constraints

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

Examples

Example 1

Input
board = standard 9x9 with one duplicate in column 0
Output
false

Example 2

Input
board = standard valid partial fill
Output
true

Approaches

1. Three separate passes (rows, cols, boxes)

Loop once per dimension; verify each row/col/box separately.

Time
O(81)
Space
O(9)
// Three nested loops: one over rows, one over cols, one over 3x3 boxes.
// Works but allocates more code than needed.

Tradeoff: Triplicate code. Datadog will push for the single-pass version.

2. Single pass with composite keys (optimal)

One Set. For each cell, insert three composite keys: ('row', i, val), ('col', j, val), ('box', i/3, j/3, val). Duplicate insert = invalid.

Time
O(81)
Space
O(81)
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 rowKey = `r${i}-${v}`;
      const colKey = `c${j}-${v}`;
      const boxKey = `b${Math.floor(i/3)}-${Math.floor(j/3)}-${v}`;
      if (seen.has(rowKey) || seen.has(colKey) || seen.has(boxKey)) return false;
      seen.add(rowKey); seen.add(colKey); seen.add(boxKey);
    }
  }
  return true;
}

Tradeoff: Single pass, three checks per cell. Datadog-canonical: the composite-key Set is the same pattern they use for multi-dim tag validation.

Datadog-specific tips

Datadog grades on whether you reach for the single-pass composite-key idiom. They'll follow up with: 'Now do this for an N x N board where N can vary' — same algorithm, the box index calculation changes to use sqrt(N) instead of hardcoded 3.

Common mistakes

  • Hardcoding box indices i/3 and j/3 as 3 instead of Math.floor — JS division returns float.
  • Forgetting '.' check — the empty marker isn't a digit.
  • Using three separate Sets and forgetting to clear them between rows — bug.

Follow-up questions

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

  • Sudoku Solver (LC 37) — backtracking on top of this validator.
  • N-Queens (LC 51) — analogous constraint encoding (row + diag + antidiag).
  • Datadog-style: validate multi-dim metric tags in one ingestion pass.

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?

One Set is simpler than three. The key encodes both the constraint dimension and the value, so duplicates within ANY dimension are caught uniformly.

Could you use bitmasks instead of Sets?

Yes — 9 bits per row/col/box. Faster (no hashing) and uses O(27 * 9) bits total. Standard performance optimization for hot-loop validation.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →