34. Valid Sudoku

Scan every filled cell once, tracking the digits already seen in each row, each column, and each 3x3 box using nine sets each. If a digit is already present in its row, column, or box, the board is invalid.

Idea

Validity is three independent no-duplicate constraints (rows, columns, boxes). We can check all three in a single pass by keeping a seen set for each of the 9 rows, 9 columns, and 9 boxes. The box index for cell (i, j) is (i // 3) * 3 + j // 3.

Algorithm

1. Create rows[9], cols[9], boxes[9] sets.
2. For each cell (i, j): skip '.'. Let b = (i//3)*3 + j//3. If v is already in rows[i], cols[j], or boxes[b], return false. Otherwise add v to all three.
3. Return true.

Worked example

A board where the only change is a second 8 in the top-left box/column is caught the moment we reach the duplicate → false. A board with no repeats in any unit passes → true.

Complexity

• Time: O(1) — a fixed 81 cells.
• Space: O(1) — 27 bounded sets.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rows = new HashSet[9];
        Set<Character>[] cols = new HashSet[9];
        Set<Character>[] boxes = new HashSet[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char v = board[i][j];
                if (v == '.') {
                    continue;
                }
                int b = (i / 3) * 3 + j / 3;
                if (rows[i].contains(v) || cols[j].contains(v) || boxes[b].contains(v)) {
                    return false;
                }
                rows[i].add(v);
                cols[j].add(v);
                boxes[b].add(v);
            }
        }
        return true;
    }
}