7.Valid Sudoku

MediumArrays & Hashing · 7/9

Problem

Determine whether a partially filled 9 x 9 Sudoku board is valid. Only the filled cells need to be checked, against three rules:

Each row contains the digits 1-9 at most once.
Each column contains the digits 1-9 at most once.
Each of the nine 3 x 3 sub-boxes contains the digits 1-9 at most once.

Empty cells are marked '.'. A valid board is not necessarily solvable — we only check that no rule is currently broken.

Examples

Input:  board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Explanation: No row, column or 3x3 box repeats a digit.

Input:  board = the same board, but board[0][0] = "8" instead of "5"
Output: false
Explanation: Column 0 now has two 8s (rows 0 and 3), and the top-left box also has two 8s (board[0][0] and board[2][2]).

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit '1'-'9' or '.'.

💡 Key Insight

Every filled cell belongs to exactly one row, one column and one box, and the box index is (r / 3) * 3 + (c / 3). If we keep a "seen" record per row, per column and per box, a single pass over the 81 cells detects any repeat the moment it appears. Because digits are only 1-9, those records can be tiny boolean arrays or even bit masks.

Three Separate Passes

TimeO(81) = O(1)SpaceO(9) = O(1)

Intuition

Check each rule independently: scan all rows, then all columns, then all boxes. For each unit, use a fresh HashSet and report a duplicate if a digit is added twice.

Algorithm

For each row r: new set; for each c, if the cell is a digit and already in the set, return false.
For each column c: same, iterating over r.
For each box b (0..8): its top-left is (3 * (b / 3), 3 * (b % 3)); scan the 9 cells with a new set.
Return true.

Visualization

Box numbering (b) and top-left cell:

 b=0 (0,0) | b=1 (0,3) | b=2 (0,6)
 b=3 (3,0) | b=4 (3,3) | b=5 (3,6)
 b=6 (6,0) | b=7 (6,3) | b=8 (6,6)

Code

java

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

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Rule 1: rows
        for (int r = 0; r < 9; r++) {
            Set<Character> seen = new HashSet<>();
            for (int c = 0; c < 9; c++) {
                char ch = board[r][c];
                if (ch != '.' && !seen.add(ch)) {
                    return false;
                }
            }
        }
        // Rule 2: columns
        for (int c = 0; c < 9; c++) {
            Set<Character> seen = new HashSet<>();
            for (int r = 0; r < 9; r++) {
                char ch = board[r][c];
                if (ch != '.' && !seen.add(ch)) {
                    return false;
                }
            }
        }
        // Rule 3: 3x3 boxes
        for (int b = 0; b < 9; b++) {
            Set<Character> seen = new HashSet<>();
            int startRow = (b / 3) * 3;
            int startCol = (b % 3) * 3;
            for (int r = startRow; r < startRow + 3; r++) {
                for (int c = startCol; c < startCol + 3; c++) {
                    char ch = board[r][c];
                    if (ch != '.' && !seen.add(ch)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

Complexity

Time: O(81) = O(1) — each cell is visited three times. For an n x n board this is O(n²).
Space: O(9) = O(1) — one set of at most 9 digits at a time.

One Pass with Hash Sets

TimeO(81) = O(1)SpaceO(81) = O(1)

Intuition

Instead of three sweeps, keep all 27 sets alive at once: 9 for rows, 9 for columns, 9 for boxes. Each filled cell is checked against its row set, column set and box set in the same visit.

Algorithm

Create rows[9], cols[9], boxes[9] arrays of HashSet<Character>.
For each cell (r, c) with digit d:
- b = (r / 3) * 3 + c / 3.
- If d is in rows[r], cols[c] or boxes[b], return false.
- Add d to all three.
Return true.

Visualization

flowchart LR
    A["cell (4,5) = 3"] --> B["row 4 set"]
    A --> C["col 5 set"]
    A --> D["box (4/3)*3 + 5/3 = 4"]
    B --> E{"3 already in<br/>any of the three?"}
    C --> E
    D --> E
    E -->|"yes"| F["return false"]
    E -->|"no"| G["add 3 to all three, continue"]

Code

java

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

class Solution {
    public boolean isValidSudoku(char[][] board) {
        @SuppressWarnings("unchecked")
        Set<Character>[] rows = new HashSet[9];
        @SuppressWarnings("unchecked")
        Set<Character>[] cols = new HashSet[9];
        @SuppressWarnings("unchecked")
        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 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; // which 3x3 box this cell belongs to
                if (rows[r].contains(d) || cols[c].contains(d) || boxes[b].contains(d)) {
                    return false;
                }
                rows[r].add(d);
                cols[c].add(d);
                boxes[b].add(d);
            }
        }
        return true;
    }
}

Complexity

Time: O(81) = O(1) — one visit per cell, O(1) set operations each.
Space: O(81) = O(1) — at most 81 digits stored per family of sets.

One Pass with Bit MasksOptimal

TimeO(81) = O(1)SpaceO(27) = O(1)

Intuition

Each row, column and box only needs to remember which of 9 digits it has seen — that fits in the low 9 bits of an int. Digit d maps to bit 1 << (d - '1'). Testing membership is mask & bit, inserting is mask |= bit. This removes boxing, hashing and object allocation entirely.

Algorithm

Create int[] rows = new int[9], cols, boxes.
For each filled cell (r, c):
- bit = 1 << (board[r][c] - '1'), b = (r / 3) * 3 + c / 3.
- If (rows[r] | cols[c] | boxes[b]) & bit is non-zero, return false.
- Set the bit in all three masks.
Return true.

Dry Run

First row of the example: 5 3 . . 7 . . . .

(0,0)='5' bit=000010000  rows[0]=000010000  boxes[0]=000010000
(0,1)='3' bit=000000100  rows[0]=000010100  boxes[0]=000010100
(0,4)='7' bit=001000000  rows[0]=001010100  boxes[1]=001000000

If the board had another '5' at (2,2):
  boxes[0] & 000010000 != 0 → return false

Code

java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] boxes = new int[9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char ch = board[r][c];
                if (ch == '.') {
                    continue;
                }
                int bit = 1 << (ch - '1');   // digit 1..9 -> bit 0..8
                int b = (r / 3) * 3 + c / 3; // box index 0..8
                if (((rows[r] | cols[c] | boxes[b]) & bit) != 0) {
                    return false; // digit already seen in this row, column or box
                }
                rows[r] |= bit;
                cols[c] |= bit;
                boxes[b] |= bit;
            }
        }
        return true;
    }
}

Complexity

Time: O(81) = O(1) — one pass, constant work per cell.
Space: O(27) = O(1) — 27 integers.

Complexity Comparison

Approach	Time	Space
Three Separate Passes	O(1) (3 × 81 cells)	O(1)
One Pass with Hash Sets	O(1) (81 cells)	O(1) (up to 243 entries)
One Pass with Bit Masks	O(1) (81 cells)	O(1) (27 ints)

Common Pitfalls

Wrong box index: r / 3 + c / 3 collides (e.g. boxes (0,1) and (1,0) both give 1). It must be (r / 3) * 3 + c / 3.
Treating '.' as a value — adding it to a set reports a false duplicate on the second empty cell.
Trying to solve the board. Validity only means no current conflicts; an unsolvable but conflict-free board is still valid.
Using ch - '0' as a shift amount gives bits 1..9; that works too, but mixing it with ch - '1' elsewhere causes silent mismatches.