Valid Sudoku

MediumMatrix · Hashing · Bitmask🧩 Matrix Traversal LeetCode #36 ↗Updated Oct 30, 2026

Problem

You are given a partly filled 9 x 9 Sudoku grid of chars, where '.' marks an empty cell. Decide whether the digits placed so far break any rule: no digit 1-9 may appear twice in the same row, the same column, or the same 3 x 3 box. You do not need to check whether the puzzle can actually be solved.

Inputa standard puzzle with 30 clues and no repeatsOutputtrue

Inputsame grid but the top-left cell changed from '5' to '8' (column 0 already has an 8)Outputfalse

board is 9 x 9 · each cell is a digit '1'-'9' or '.'

Try it yourself

Java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Every filled cell belongs to exactly three units: row r, column c and box (r/3)*3 + c/3. Keep a “seen” record per unit and the whole check becomes one pass over the 81 cells.

PatternMatrix Traversal

Instinct A 2D grid you must walk in a fixed geometric order (spiral, diagonal, layer, rotate) or update in place - think boundaries, direction vectors and index maths.

Memory hack Walk the walls, then shrink the room - four fences (top, bottom, left, right) close in after every lap.

Open the Matrix Traversal guide →

Approaches

Brute ForceRescan Row, Column and Box per Cell

Time O(N³)Space O(1)

For each filled cell, walk its row, its column and its box and see whether any other cell holds the same digit. Any hit means the board is invalid. With N = 9 that is 81 cells × ~27 comparisons.

Java

public boolean isValidSudoku(char[][] board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char d = board[r][c];
            if (d == '.') continue;
            for (int k = 0; k < 9; k++) {
                if (k != c && board[r][k] == d) return false;   // same row
                if (k != r && board[k][c] == d) return false;   // same column
            }
            int br = r / 3 * 3, bc = c / 3 * 3;
            for (int i = br; i < br + 3; i++) {
                for (int j = bc; j < bc + 3; j++) {
                    if ((i != r || j != c) && board[i][j] == d) return false; // same box
                }
            }
        }
    }
    return true;
}

No extra memory, but repeats the same comparisons many times.

BetterOne Pass with Hash Sets

Time O(N²)Space O(N²)

Keep one HashSet per row, per column and per box (27 sets). Each filled cell tries to add its digit to its three sets; add returning false means the digit was already there — a duplicate.

Java

public boolean isValidSudoku(char[][] board) {
    List<Set<Character>> rows = new ArrayList<>(), cols = new ArrayList<>(),
                         boxes = new ArrayList<>();
    for (int i = 0; i < 9; i++) {
        rows.add(new HashSet<>());
        cols.add(new HashSet<>());
        boxes.add(new HashSet<>());
    }
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char d = board[r][c];
            if (d == '.') continue;
            int b = (r / 3) * 3 + c / 3;
            if (!rows.get(r).add(d) || !cols.get(c).add(d) || !boxes.get(b).add(d)) {
                return false;
            }
        }
    }
    return true;
}

Single pass and easy to explain; hashing adds constant-factor overhead.

OptimalOne Pass with Bitmasks

Time O(N²)Space O(N)

Replace each set by a 9-bit integer: bit d is on once digit d has been seen in that unit. Testing and inserting are a single & and |, so the whole state is just 27 ints.

Java

public boolean isValidSudoku(char[][] board) {
    int[] rows = new int[9], cols = new int[9], boxes = new int[9];
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') continue;
            int bit = 1 << (board[r][c] - '1');
            int b = (r / 3) * 3 + c / 3;
            if ((rows[r] & bit) != 0 || (cols[c] & bit) != 0 || (boxes[b] & bit) != 0) {
                return false; // digit already seen in one of its units
            }
            rows[r] |= bit;
            cols[c] |= bit;
            boxes[b] |= bit;
        }
    }
    return true;
}

Same single pass, tiny fixed memory and no boxing — the cleanest answer.

Pro tip

Derive the box index on the whiteboard: (r / 3) * 3 + c / 3 numbers the boxes 0-8 left-to-right, top-to-bottom.

At a glance

Level	Approach	Time	Space
Brute Force	Rescan Row, Column and Box per Cell	`O(N³)`	`O(1)`
Better	One Pass with Hash Sets	`O(N²)`	`O(N²)`
Optimal	One Pass with Bitmasks	`O(N²)`	`O(N)`

Common pitfalls

Getting the box index wrong, e.g. r / 3 + c / 3 (collides boxes).
Trying to solve the puzzle — only the current placements must be checked.
Forgetting to skip '.' cells, which then look like duplicates of each other.

Interview tips

Clarify: valid ≠ solvable.
Point out that with a fixed 9 x 9 board everything is technically O(1); state it in N too.
Offer the bitmask version as the memory-lean refinement of the hash sets.

Pattern

Per-group seen sets → detect duplicates within overlapping groups (rows, columns, blocks) in one scan.

My notes saved in this browser