Valid Sudoku
Medium · Arrays & Hashing · Array · Hash Table · Matrix
Problem
You are given a 9 x 9 Sudoku board as a grid of characters, where each cell is a digit '1'-'9' or '.' for an empty cell.
Return true if the filled cells are consistent with the Sudoku rules: no digit repeats within a row, within a column, or within any of the nine 3 x 3 boxes. Only the filled cells need to be checked; the board does not have to be solvable.
Examples
Input: board = [["1",".",".",".",".",".",".",".","."],[".","2",".",".",".",".",".",".","."],[".",".","3",".",".",".",".",".","."],[".",".",".","4",".",".",".",".","."],[".",".",".",".","5",".",".",".","."],[".",".",".",".",".","6",".",".","."],[".",".",".",".",".",".","7",".","."],[".",".",".",".",".",".",".","8","."],[".",".",".",".",".",".",".",".","9"]] Output: true
Each digit appears once, on the main diagonal, so no row, column or box has a repeat.
Input: board = [["1",".",".",".",".",".",".",".","."],[".","2",".",".",".",".",".",".","."],[".","1","3",".",".",".",".",".","."],[".",".",".","4",".",".",".",".","."],[".",".",".",".","5",".",".",".","."],[".",".",".",".",".","6",".",".","."],[".",".",".",".",".",".","7",".","."],[".",".",".",".",".",".",".","8","."],[".",".",".",".",".",".",".",".","9"]] Output: false
The '1' added at row 2, column 1 shares the top-left box with the '1' at (0, 0), though not its row or column.
Input: board = [["1",".",".",".",".",".",".",".","."],[".","2",".",".",".",".",".",".","."],[".",".","3",".",".",".",".",".","."],[".",".",".","4",".",".",".",".","."],[".",".",".",".","5",".",".",".","."],[".",".",".",".",".","6",".",".","."],[".",".",".",".",".",".","7",".","."],[".",".",".",".",".",".",".","8","."],["1",".",".",".",".",".",".",".","9"]] Output: false
The '1' added at row 8 shares column 0 with the '1' in row 0.
Constraints
- len(board) == 9
- len(board[i]) == 9
- board[i][j] is a digit '1'-'9' or '.'
Approaches
- Baseline: scan each digit's row, column and box — time O(81 · 27), space O(1)
Follow-up
Checking is not solving: a board can pass every rule and still have no solution. Solving needs backtracking over the empty cells, using these same row, column and box records to reject a digit in O(1).
Related problems
Start free on Cariara · Coding problems · System design studio
