How do you find which 3×3 box a cell is in?

Integer-divide the row and column by 3: (r / 3) picks the box's row band and (c / 3) its column band, so box = (r / 3) * 3 + c / 3 numbers the nine boxes 0 to 8, left to right and top to bottom.

Does a valid board have to be solvable?

No. The problem only asks whether the filled cells break the rules: no digit repeated in a row, a column or a box. A board can pass that check and still have no solution.

Why is the complexity O(1)?

The board is always 9 × 9, so the loop runs at most 81 times and the sets hold at most 81 digits in total. For an n × n Sudoku the same method is O(n²).

Valid Sudoku

Check that a partly filled Sudoku board has no repeated digit in any row, column or 3×3 box, in one pass with hash sets.

MediumSolve on LeetCode

Problem Understanding

Valid Sudoku: given a 9 × 9 board where some cells hold digits 1–9 and the rest are empty (.), decide whether the filled cells follow the rules: no digit appears twice in any row, any column, or any of the nine 3 × 3 boxes.

Only the filled cells are checked; the board does not need to be solvable.

Attempt 1: Three Separate Passes

Check every row for repeats, then every column, then every box, each with its own set. That is correct and still O(81), but it reads the board three times. One pass can do all three checks at once, with nine sets for each kind of group.

The Intuition: Every Digit Belongs to Three Groups

A digit at (r, c) belongs to exactly three groups: row r, column c, and box b = (r / 3) * 3 + c / 3. Keep a set for each of the 27 groups. Visit the cells once:

Skip empty cells.
If the digit is already in its row, column or box set, the board is invalid.
Otherwise add it to all three.

The box formula is the only trick: dividing by 3 turns the 0–8 row and column into a 0–2 band, and the two bands together name one of nine boxes.

Interactive Walkthrough

The cells are checked in row order. The current cell is filled and its row, column and box are shaded, which are exactly the three sets it is checked against. On a repeat, the earlier copy of the digit turns red.

Dry Run Table

LeetCode example 2 (the top-left 5 changed to 8):

Cell	Digit	Row	Col	Box	Result
(0, 0)	8	new	new	new	record
(0, 1)	3	new	new	new	record
…
(2, 1)	9	new	new	new	record
(2, 2)	8	new	new	8 already in box 0	return false

The repeat is caught by the box set, before the column 0 repeat further down is ever reached.

The Solution Template

One pass over the board with a set (or a boolean table) per row, column and box.

Valid Sudoku Code

1var isValidSudoku = function(board) {
2    const rows = Array.from({ length: 9 }, () => new Set());
3    const cols = Array.from({ length: 9 }, () => new Set());
4    const boxes = Array.from({ length: 9 }, () => new Set());
5    for (let r = 0; r < 9; r++) {
6        for (let c = 0; c < 9; c++) {
7            const v = board[r][c];
8            if (v === '.') continue;
9            const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
10            if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) return false;
11            rows[r].add(v);
12            cols[c].add(v);
13            boxes[b].add(v);
14        }
15    }
16    return true;
17};

Edge Cases & Common Mistakes

A repeat only in a box: two 1s at (0, 0) and (1, 2) share no row or column; only the box set catches it.
Wrong box formula: r / 3 + c / 3 sends different boxes to the same number; it must be (r / 3) * 3 + c / 3.
Checking empty cells: . is not a digit and must be skipped, or every board with two empty cells looks invalid.
Trying to solve the board: not needed; validity is only about the cells already filled.

Summary

Every filled cell belongs to one row, one column and one box. Keep a set for each of the 27 groups, check each digit against its three sets, and record it if it is new. One pass over 81 cells.

More practice: DSA interview questions with answers · patterns cheat sheet

Longest Consecutive Sequence

Majority Element