Valid Sudoku

mediumAmazon-tagged: Mixed406 stepsJava · Python · C++

Check that the filled cells of a 9×9 board break no rule: no repeated digit in any row, column, or 3×3 box. Scan every cell once and record keys like "5 in row 0", "5 in col 3", "5 in box 1" in a set; a failed insert means a repeat.

▶ Watch the animated trace

Traced input: board = LeetCode example 1 (valid) → true. Original problem: neetcode.io/problems/valid-sudoku

Complexity

BestO(1)

AverageO(81)

WorstO(81)

SpaceO(81)

The board size is fixed.

Key idea

The box index of (r, c) is (r / 3) * 3 + c / 3.
One set of string keys covers all three rules.
Empty cells ('.') are ignored; the board doesn't need to be solvable.

Common mistakes

Trying to check solvability; the problem only asks about the current cells.
Getting the box index formula wrong.

Solution

Java

boolean isValidSudoku(char[][] board) {
    Set<String> seen = 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 box = (r / 3) * 3 + c / 3;
            boolean fresh = seen.add(d + " in row " + r) && seen.add(d + " in col " + c) && seen.add(d + " in box " + box);
            if (!fresh) {
                return false;
            }
        }
    return true;
}

Python

def isValidSudoku(board: List[List[str]]) -> bool:
    seen = set()
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == '.': continue
            keys = (f"{d} in row {r}", f"{d} in col {c}", f"{d} in box {(r // 3) * 3 + c // 3}")
            if any(k in seen for k in keys):
                return False
            seen.update(keys)
    return True

C++

bool isValidSudoku(vector<vector<char>>& board) {
    unordered_set<string> seen;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            char d = board[r][c];
            if (d == '.') continue;
            string dd(1, d), box = to_string((r / 3) * 3 + c / 3);
            bool fresh = seen.insert(dd + " in row " + to_string(r)).second && seen.insert(dd + " in col " + to_string(c)).second && seen.insert(dd + " in box " + box).second;
            if (!fresh) {
                return false;
            }
        }
    return true;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Repeat in a box Two 8s in the first column (and the top-left box).	`board = example 1 with an 8 at the top-left`	`false`
Empty board No digits, no conflicts.	`board = all '.'`	`true`