Skip to content
16-Week DSA Roadmap
LeetCode #36MediumProblem 7 of 8

Valid Sudoku

Check that no digit repeats in any row, column or 3×3 box of a partly filled Sudoku board.

  • Encoding constraints as set keys
  • Hash set membership

Before this, know: 2D arrays (a list of rows), Hash sets (Set in JavaScript, set in Python), Integer division (// in Python, Math.floor in JavaScript)

The problem in plain English

A Sudoku board is a 9 × 9 grid. Some cells hold a digit "1" to "9"; empty cells hold ".". The board is stored as a 2D array: an array of 9 rows, where each row is an array of 9 cells. board[r][c] is the cell in row r and column c, both counted from 0.

The board is valid when no digit appears twice in:

  • the same row,
  • the same column, or
  • the same 3 × 3 box (the nine bold-bordered squares).

Return true if the filled cells follow these rules, false otherwise.

012345678
0
5
3
7
1
6
1
9
5
2
9
8
6
3
8
6
3
The top-left corner of LeetCode's example. The shaded cells are row 0, column 0 and box 0: the three units the 5 at (0, 0) belongs to.

The rules that matter:

  • Only the filled cells are checked. Empty cells are ignored.
  • The board doesn’t have to be solvable. We only check for repeats.
  • The digits are stored as strings ("5", not 5).

Before you code: think it through

Each of those guest lists is a hash set: a collection that answers “is this value in here?” in about one step. We need 9 row sets, 9 column sets and 9 box sets: 27 sets in total.

The tricky part is knowing which box a cell is in. The boxes are numbered 0 to 8, left to right and top to bottom, and the formula is:

box = (r // 3) * 3 + (c // 3)

Here // means integer division: divide and throw away the remainder (7 // 3 is 2). r // 3 tells us which band of three rows we’re in (0, 1 or 2), and c // 3 which stack of three columns (0, 1 or 2). Each band holds 3 boxes, so we multiply the band by 3 and add the stack.

012345678001122334455667788cell (4, 7): box = (4 // 3) × 3 + 7 // 3box = 1 × 3 + 2 = 5
Cell (4, 7) is in band 4 // 3 = 1 and stack 7 // 3 = 2, so its box is 1 × 3 + 2 = 5.

Pause and think

Which box is cell (8, 0) in? And cell (2, 5)?

Approach 1: Brute force

For every filled cell, scan the other 8 cells of its row, the other 8 of its column and the other 8 of its box, looking for the same digit. One loop variable k from 0 to 8 visits the k-th cell of each unit at once.

Brute force: scan row, column and box for every digit

Two 5s in the same box

012345678
0
5
3
1
5
2
3
4
5
6
7
8
variables
k
0
cells looked at
3
  • Digit we're checking
  • Cells compared at this k
  • Same digit found

Checking 5 at (0, 0), k = 0: look at (0, 0) in its row, (0, 0) in its column and (0, 0) in its box. No other 5. (3 cells looked at so far.)

Step 1 / 5

Which line is running?

function isValidSudoku(board) {  for (let r = 0; r < 9; r++) {    for (let c = 0; c < 9; c++) {      const d = board[r][c];      if (d === ".") continue; // empty cell: nothing to checkRunning now:       for (let k = 0; k < 9; k++) {        // k-th cell of the same row, the same column and the same box        const br = Math.floor(r / 3) * 3 + Math.floor(k / 3);        const bc = Math.floor(c / 3) * 3 + (k % 3);        if (k !== c && board[r][k] === d) return false;        if (k !== r && board[k][c] === d) return false;        if ((br !== r || bc !== c) && board[br][bc] === d) return false;      }    }  }  return true;}

Brute force: scan the three units

function isValidSudoku(board) {  for (let r = 0; r < 9; r++) {    for (let c = 0; c < 9; c++) {      const d = board[r][c];      if (d === ".") continue; // empty cell: nothing to check      for (let k = 0; k < 9; k++) {        // k-th cell of the same row, the same column and the same box        const br = Math.floor(r / 3) * 3 + Math.floor(k / 3);        const bc = Math.floor(c / 3) * 3 + (k % 3);        if (k !== c && board[r][k] === d) return false;        if (k !== r && board[k][c] === d) return false;        if ((br !== r || bc !== c) && board[br][bc] === d) return false;      }    }  }  return true;}
def is_valid_sudoku(board):    for r in range(9):        for c in range(9):            d = board[r][c]            if d == ".":                continue  # empty cell: nothing to check            for k in range(9):                # k-th cell of the same row, the same column and the same box                br = (r // 3) * 3 + k // 3                bc = (c // 3) * 3 + k % 3                if k != c and board[r][k] == d:                    return False                if k != r and board[k][c] == d:                    return False                if (br, bc) != (r, c) and board[br][bc] == d:                    return False    return True

The two lines computing br and bc find the k-th cell of the box: the box’s top-left corner is at ((r // 3) * 3, (c // 3) * 3), and k walks across it 3 cells per row.

Why is it slow?

Each filled cell makes 24 reads: the other 8 cells of its row, of its column and of its box. (k runs 9 times with 3 checks each, which is 27, minus the 3 times k lands on the cell itself.) A full board has 81 cells, so up to 81 × 24 = 1,944 cell reads. The board is always 9 × 9, so technically this is a fixed amount of work. But if the board were n × n, every cell would scan about 3n others: n² cells × 3n. In Big-O notation (a short way of saying how the work grows as the input grows; see Big-O in 5 minutes) that’s O(n³). The better idea does each cell in a handful of lookups.

The pattern: encoding constraints as set keys

The brute force keeps re-reading the board to answer “is there already a 5 in this row?”. Instead we can remember the answer as we go: each rule (“no repeat in row r”) becomes a set, and the fact “5 is in row 0” becomes an entry in that set.

Pattern

Encoding constraints as set keys

Template

Use it when: several rules must hold at once, and each rule is 'no repeats within some group'.

Signal words

  • “valid sudoku”
  • “no repeats in each row/column”
  • “each group must be unique”
  • “N-Queens”
  • “placed already”

Approach 2: One pass with 27 sets

  1. Make 9 empty sets for rows, 9 for columns and 9 for boxes.
  2. Visit every cell, row by row. Skip empty cells (".").
  3. For a digit d at (r, c), work out its box: b = (r // 3) * 3 + c // 3.
  4. If d is already in rows[r], cols[c] or boxes[b], return false.
  5. Otherwise add d to all three sets.
  6. If we finish the board, return true.

Press Play. The shaded cells are the row, column and box of the current cell; below the board you see exactly those three sets and the lookups. Start with LeetCode’s invalid example: the top-left cell is an 8, and box 0 already has another 8 further in. Then try the row and column clashes, where a different set catches the repeat. The last example runs the whole valid board (with check and add shown as one step to keep it short).

One pass with 27 sets

LeetCode example 2: the top-left cell is 8 instead of 5

012345678
0
8
3
7
1
6
1
9
5
2
9
8
6
3
8
6
3
4
4
8
3
1
5
7
2
6
6
6
2
8
7
4
1
9
5
8
8
7
9
variables
r
—
c
—
d
—the digit
b
—
answer
—
  • Cell we're checking
  • Its row, column and box
  • Repeated digit
  • Just added to a set

Make 27 empty sets: one per row, one per column and one per 3×3 box. Each set will remember which digits that unit already contains. We only check the filled cells; empty ones ('.') are skipped.

Step 1 / 19

Which line is running?

function isValidSudoku(board) {  // 9 sets for the rows, 9 for the columns, 9 for the 3x3 boxesRunning now:   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 d = board[r][c];      if (d === ".") continue; // empty cell: nothing to check      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); // box 0..8      if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) {        return false; // d is already in this row, column or box      }      rows[r].add(d);      cols[c].add(d);      boxes[b].add(d);    }  }  return true;}

The code, line by line

One pass with 27 sets

function isValidSudoku(board) {  // 9 sets for the rows, 9 for the columns, 9 for the 3x3 boxes  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 d = board[r][c];      if (d === ".") continue; // empty cell: nothing to check      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); // box 0..8      if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) {        return false; // d is already in this row, column or box      }      rows[r].add(d);      cols[c].add(d);      boxes[b].add(d);    }  }  return true;}
def is_valid_sudoku(board):    # 9 sets for the rows, 9 for the columns, 9 for the 3x3 boxes    rows = [set() for _ in range(9)]    cols = [set() for _ in range(9)]    boxes = [set() for _ in range(9)]    for r in range(9):        for c in range(9):            d = board[r][c]            if d == ".":                continue  # empty cell: nothing to check            b = (r // 3) * 3 + c // 3  # box 0..8            if d in rows[r] or d in cols[c] or d in boxes[b]:                return False  # d is already in this row, column or box            rows[r].add(d)            cols[c].add(d)            boxes[b].add(d)    return True

Lines 1–8 match in both languages. Python spreads the “skip empty cell” check over two lines, so from there on its line numbers run one ahead.

  • Line 1: define the function. (LeetCode: var isValidSudoku = function(board) in JS, def isValidSudoku(self, board) in class Solution in Python.)
  • Lines 3–5: 27 empty sets, 9 in each list. Array.from({ length: 9 }, () => new Set()) and [set() for _ in range(9)] both create nine separate sets. rows[2] will hold the digits already seen in row 2.
  • Lines 6–7: visit every cell, row by row.
  • Line 8: read the cell. It’s a string such as "5" or ".".
  • Line 9 (JS) / lines 9–10 (Python): continue skips the rest of the loop body for an empty cell and moves to the next one.
  • Line 10 (JS) / line 11 (Python): the box number. JavaScript has no //, so we write Math.floor(r / 3), which rounds down the same way.
  • Line 11 (JS) / line 12 (Python): three lookups, about one step each. If any finds d, the board breaks a rule.
  • Line 12 (JS) / line 13 (Python): return false at the first repeat.
  • Lines 14–16 (both): record d in its row, column and box sets.
  • Last line: no repeats anywhere, so the board is valid.

The same idea with one set

Instead of 27 sets, you can use one set and put the unit into the key itself: "5 in row 0", "5 in col 0", "5 in box 0". Each filled cell makes three keys; if any key already exists, a rule is broken. It’s the same logic, written as “encode the constraint as a key”.

One set with descriptive keys

function isValidSudoku(board) {  const seen = new Set(); // one set, with the unit written into the key  for (let r = 0; r < 9; r++) {    for (let c = 0; c < 9; c++) {      const d = board[r][c];      if (d === ".") continue;      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);      const keys = [`${d} in row ${r}`, `${d} in col ${c}`, `${d} in box ${b}`];      for (const key of keys) {        if (seen.has(key)) return false;        seen.add(key);      }    }  }  return true;}
def is_valid_sudoku(board):    seen = set()  # one set, with the unit written into the key    for r in range(9):        for c in range(9):            d = board[r][c]            if d == ".":                continue            b = (r // 3) * 3 + c // 3            for key in ((d, "row", r), (d, "col", c), (d, "box", b)):                if key in seen:                    return False                seen.add(key)    return True

In Python the key is a tuple like ("5", "row", 0), which a set can store directly.

Dry run

The first few filled cells of LeetCode’s invalid example (an 8 at (0, 0)):

celldboxin rows[r]?in cols[c]?in boxes[b]?result
(0, 0)80nononoadd 8 to row 0, col 0, box 0
(0, 1)30nononoadd 3
(0, 4)71nononoadd 7
(1, 0)60nononoadd 6
(1, 3) … (1, 5)1, 9, 51nononoadd each
(2, 1)90nononoadd 9
(2, 2)80nonoyesreturn false
LeetCode example 2, top-left 8

At (2, 2) neither row 2 nor column 2 has an 8 yet, so the first two lookups pass. But boxes[0] already holds the 8 from (0, 0): both cells sit in the top-left box. (Column 0 also has two 8s, at (0, 0) and (3, 0), but we stop at the first broken rule we meet.)

Complexity

Brute force

Time

O(1) here, O(n³) for an n × n board

Each of 81 cells reads 24 others: at most 1,944 reads. For an n × n board that grows like n² × 3n.

Space

O(1)

Only a few loop variables.

27 sets

Time

O(1) here, O(n²) for an n × n board

Each of 81 cells does 3 lookups and 3 inserts, about 6 steps: under 500 steps. For n × n it's proportional to the number of cells.

Space

O(1) here, O(n²) in general

At most 81 digits, each stored in 3 sets.

Because a Sudoku board never grows, both are technically O(1). Say so in an interview, then explain how each would scale for an n × n board. That shows you understand what Big-O measures.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “Three rules: unique per row, per column, per box. Only filled cells count.”
  2. “I’ll keep a set per row, column and box. The box index is (r // 3) * 3 + c // 3.”
  3. “One pass: for each digit, three lookups and three inserts.”
  4. “The board is fixed at 9 × 9, so it’s O(1), or O(n²) for an n × n board.”

Likely follow-up questions:

  • “Can you do it with one set?” Yes: encode the unit in the key (shown above).
  • “Can you use bits instead of sets?” Each unit can be a 9-bit number where bit d is set when digit d is present. Same idea, smaller memory.
  • “Now solve the Sudoku.” That’s Sudoku Solver, a backtracking problem, and these same three sets make each “can I place d here?” check instant.

Related problems:

  • Contains Duplicate (this week): one set, one rule. Valid Sudoku is 27 of those at once.
  • Group Anagrams (this week): designing the right key is the whole trick there too.