Valid Sudoku

Problem in Plain English

Given a partially filled 9 x 9 Sudoku board where empty cells are written as ., decide whether the filled cells obey the Sudoku rules: no digit 1-9 may repeat within any row, any column, or any of the nine 3 x 3 sub-boxes. A board can be valid without being solvable.

Problem Statement

Determine whether a partially filled 9 x 9 Sudoku board is valid. Only the filled cells must satisfy the rules: each row, each column, and each of the nine 3 x 3 sub-boxes must contain the digits 1-9 without repetition.

Empty cells are written as . and are ignored. A board that follows these rules is valid even if it could never be completed into a solved puzzle.

Constraints

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

Examples

Example 1

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

No row, column or 3 x 3 sub-box contains a repeated digit, so the filled cells satisfy every rule.

Example 2

Input: board = [["8","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: false

Changing the top-left 5 to 8 creates a box conflict with 8 at (2, 2) in box 0. It also repeats 8 in column 0 at rows 0 and 3. Either violation is enough to return false.

Example 3

Input: board = [[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]
Output: true

All 81 cells are empty, so there are no filled digits to violate a row, column, or box rule.

Example 4

Input: board = [["4",".",".",".",".",".",".",".","."],[".","4",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]
Output: false

The two 4s use different rows and columns, but both belong to the top-left 3-by-3 box. Only the box rule fails.

Example 5

Input: board = [["4",".",".","4",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]
Output: false

Two 4s share row 0 but use different columns and different boxes. Only the row rule fails.

Example 6

Input: board = [["4",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],["4",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]
Output: false

Two 4s share column 0 but use different rows and different boxes. Only the column rule fails.

Intuition

Each filled cell belongs to three groups: its row, its column, and its 3-by-3 box. A digit is legal only when none of those groups already contains it. Example 1 puts 5 at (0, 0), so row 0, column 0, and box 0 each remember 5. A later 5 in any one of those groups would be a conflict; a 5 in unrelated groups is allowed. Empty cells carry no digit and are skipped. This checks existing clues, not whether a solver can finish the puzzle.

Approaches

Three Separate Passes

Solution Details

Reveal Three Separate Passes: intuition, complexity, and code

Intuition

Validate each group independently using a fresh seen collection: all nine rows, all nine columns, then all nine boxes. Reusing one small collection reduces simultaneous storage, at the cost of scanning each cell three times.

Step-by-Step Logic

Check each row from left to right. Start a fresh seen collection for that row, skip dots, and return false if a digit is already present before inserting it. Example 1 row 0 records 5, 3, then 7.
Repeat the same rule for each column from top to bottom, resetting seen for every column. Example 1 column 0 records 5, 6, 8, 4, then 7.
For every box numbered 0 through 8, compute its top-left cell as (box / 3) * 3 and (box % 3) * 3, using integer division. Scan those three rows and three columns with a fresh collection.
Example 1 box 0 records 5, 3, 6, 9, then 8. Continue through every box; do not stop after rows and columns alone pass.
Return true only after all 27 groups finish without a duplicate. The table shows every filled insertion in every group; dots perform no insertion.

Why It Works

A row, column, or box passes exactly when its filled digits have no repeats: seen contains precisely the digits already visited in that group. A membership hit therefore proves two cells violate that group rule. Resetting seen prevents unrelated groups from interfering. All required groups are checked, so passing every group is equivalent to satisfying every Sudoku validation rule.

Dry Run

Three Separate Passes: variable states at each step
Pass	Group and reset	Filled cells in scan order	Seen after each insertion	Result
Row	`0`, start `{}`	`(0,0)=5; (0,1)=3; (0,4)=7`	`{} -> {5} -> {5,3} -> {5,3,7}`	pass
Row	`1`, start `{}`	`(1,0)=6; (1,3)=1; (1,4)=9; (1,5)=5`	`{} -> {6} -> {6,1} -> {6,1,9} -> {6,1,9,5}`	pass
Row	`2`, start `{}`	`(2,1)=9; (2,2)=8; (2,7)=6`	`{} -> {9} -> {9,8} -> {9,8,6}`	pass
Row	`3`, start `{}`	`(3,0)=8; (3,4)=6; (3,8)=3`	`{} -> {8} -> {8,6} -> {8,6,3}`	pass
Row	`4`, start `{}`	`(4,0)=4; (4,3)=8; (4,5)=3; (4,8)=1`	`{} -> {4} -> {4,8} -> {4,8,3} -> {4,8,3,1}`	pass
Row	`5`, start `{}`	`(5,0)=7; (5,4)=2; (5,8)=6`	`{} -> {7} -> {7,2} -> {7,2,6}`	pass
Row	`6`, start `{}`	`(6,1)=6; (6,6)=2; (6,7)=8`	`{} -> {6} -> {6,2} -> {6,2,8}`	pass
Row	`7`, start `{}`	`(7,3)=4; (7,4)=1; (7,5)=9; (7,8)=5`	`{} -> {4} -> {4,1} -> {4,1,9} -> {4,1,9,5}`	pass
Row	`8`, start `{}`	`(8,4)=8; (8,7)=7; (8,8)=9`	`{} -> {8} -> {8,7} -> {8,7,9}`	pass
Column	`0`, start `{}`	`(0,0)=5; (1,0)=6; (3,0)=8; (4,0)=4; (5,0)=7`	`{} -> {5} -> {5,6} -> {5,6,8} -> {5,6,8,4} -> {5,6,8,4,7}`	pass
Column	`1`, start `{}`	`(0,1)=3; (2,1)=9; (6,1)=6`	`{} -> {3} -> {3,9} -> {3,9,6}`	pass
Column	`2`, start `{}`	`(2,2)=8`	`{} -> {8}`	pass
Column	`3`, start `{}`	`(1,3)=1; (4,3)=8; (7,3)=4`	`{} -> {1} -> {1,8} -> {1,8,4}`	pass
Column	`4`, start `{}`	`(0,4)=7; (1,4)=9; (3,4)=6; (5,4)=2; (7,4)=1; (8,4)=8`	`{} -> {7} -> {7,9} -> {7,9,6} -> {7,9,6,2} -> {7,9,6,2,1} -> {7,9,6,2,1,8}`	pass
Column	`5`, start `{}`	`(1,5)=5; (4,5)=3; (7,5)=9`	`{} -> {5} -> {5,3} -> {5,3,9}`	pass
Column	`6`, start `{}`	`(6,6)=2`	`{} -> {2}`	pass
Column	`7`, start `{}`	`(2,7)=6; (6,7)=8; (8,7)=7`	`{} -> {6} -> {6,8} -> {6,8,7}`	pass
Column	`8`, start `{}`	`(3,8)=3; (4,8)=1; (5,8)=6; (7,8)=5; (8,8)=9`	`{} -> {3} -> {3,1} -> {3,1,6} -> {3,1,6,5} -> {3,1,6,5,9}`	pass
Box	`0`, start `{}`	`(0,0)=5; (0,1)=3; (1,0)=6; (2,1)=9; (2,2)=8`	`{} -> {5} -> {5,3} -> {5,3,6} -> {5,3,6,9} -> {5,3,6,9,8}`	pass
Box	`1`, start `{}`	`(0,4)=7; (1,3)=1; (1,4)=9; (1,5)=5`	`{} -> {7} -> {7,1} -> {7,1,9} -> {7,1,9,5}`	pass
Box	`2`, start `{}`	`(2,7)=6`	`{} -> {6}`	pass
Box	`3`, start `{}`	`(3,0)=8; (4,0)=4; (5,0)=7`	`{} -> {8} -> {8,4} -> {8,4,7}`	pass
Box	`4`, start `{}`	`(3,4)=6; (4,3)=8; (4,5)=3; (5,4)=2`	`{} -> {6} -> {6,8} -> {6,8,3} -> {6,8,3,2}`	pass
Box	`5`, start `{}`	`(3,8)=3; (4,8)=1; (5,8)=6`	`{} -> {3} -> {3,1} -> {3,1,6}`	pass
Box	`6`, start `{}`	`(6,1)=6`	`{} -> {6}`	pass
Box	`7`, start `{}`	`(7,3)=4; (7,4)=1; (7,5)=9; (8,4)=8`	`{} -> {4} -> {4,1} -> {4,1,9} -> {4,1,9,8}`	pass
Box	`8`, start `{}`	`(6,6)=2; (6,7)=8; (7,8)=5; (8,7)=7; (8,8)=9`	`{} -> {2} -> {2,8} -> {2,8,5} -> {2,8,5,7} -> {2,8,5,7,9}`	pass
Finish	all 27 groups	each dot skipped	no duplicate in any group	return `true`

Complexity Analysis

Time Complexity

O(1)

Space Complexity

O(1)

The input is always exactly 9 by 9. Three passes inspect at most 243 cells in total, with one seen collection holding at most 9 digits at a time (Java uses 10 Boolean slots). Both time and extra space are O(1) for this fixed problem. If the board dimension were variable, three full scans would instead scale with its cell count.

Code

Solution.java

1class Solution {2    public boolean isValidSudoku(char[][] board) {3        for (int r = 0; r < 9; r++) {4            boolean[] seen = new boolean[10];5            for (int c = 0; c < 9; c++) {6                char ch = board[r][c];7                if (ch == '.') continue;8                int d = ch - '0';9                if (seen[d]) return false;10                seen[d] = true;11            }12        }13        for (int c = 0; c < 9; c++) {14            boolean[] seen = new boolean[10];15            for (int r = 0; r < 9; r++) {16                char ch = board[r][c];17                if (ch == '.') continue;18                int d = ch - '0';19                if (seen[d]) return false;20                seen[d] = true;21            }22        }23        for (int box = 0; box < 9; box++) {24            boolean[] seen = new boolean[10];25            int startRow = (box / 3) * 3;26            int startCol = (box % 3) * 3;27            for (int r = startRow; r < startRow + 3; r++) {28                for (int c = startCol; c < startCol + 3; c++) {29                    char ch = board[r][c];30                    if (ch == '.') continue;31                    int d = ch - '0';32                    if (seen[d]) return false;33                    seen[d] = true;34                }35            }36        }37        return true;38    }39}

Hints

Hint 1

A duplicate matters only inside one row, one column or one sub-box, so each filled cell needs a fast membership test against those three groups.

Hint 2

One set per row, one per column and one per sub-box lets you test and record a digit the moment you visit its cell.

Hint 3

Integer division maps a cell to its sub-box: combine r / 3 and c / 3 into a single box index from 0 to 8.

Edge Cases

An all-dot board returns true. Empty rows and boxes do not need every digit to be present.
A box-only conflict can sit at (0, 0) and (1, 1), while every row and column is individually valid.
A row-only conflict at (0, 0) and (0, 3), or column-only conflict at (0, 0) and (3, 0), must also return false.
Equal digits in unrelated groups are allowed, such as 4 at (0, 0) and (3, 3). A single global set would wrongly reject them.
Validity does not imply solvability: row 0 containing .12345678 and row 1 starting with 9 has no existing duplicate, but cell (0, 0) cannot be filled legally.
Other characters and board shapes are outside the public constraints; this exercise does not require a generalized input validator.

Common Mistakes and Interview Tips

Checking only rows and columns misses box-only conflicts. Each filled cell must also satisfy its box rule.
Using non-integer division or (r / 3) + (c / 3) gives wrong box grouping. Use floor division and multiply the box row by 3.
Recording dots makes empty cells look like duplicates. Skip them before any membership check.
Sharing one set across groups, or constructing nine references to the same set, lets unrelated cells interfere. Create an independent set for each group.
Interview tip: explain why the fixed 9-by-9 constraints make both methods O(1), then compare 243 versus 81 cell inspections and one live collection versus 27. Validation needs no backtracking or puzzle solving.

Key Takeaway

When one item must satisfy several independent group constraints at once, keep one seen-set per group and validate each item against all of them in a single pass.