Verify Sudoku Board
Given a 9x9 Sudoku board represented as a list of 9 rows, each a list of 9 characters, determine whether the board is valid. The board may be partially filled — only the filled cells need to be checked against the standard Sudoku rules:
- Each row must contain the digits
1-9with no repeats. - Each column must contain the digits
1-9with no repeats. - Each of the nine 3x3 sub-boxes must contain the digits
1-9with no repeats.
Empty cells are represented by the character "." and are ignored by
all three rules. You do not need to check whether the board is
solvable — only whether the filled-in digits violate any rule.
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
Example 2
Input: board where two "8"s appear in the same column (all else the
same as a valid board)
Output: false
Explanation: A column contains the digit 8 twice.
Constraints
board.length == 9board[i].length == 9board[i][j]is either a digit1-9or".".
The key insight is that "no repeats" is exactly a membership-checking
problem, and a hash set gives O(1) membership checks. We need three
families of sets: one per row, one per column, and one per 3x3 box.
A cell at (row, col) belongs to box index (row // 3) * 3 + (col // 3).
Scan every filled cell once. For each one, check whether its digit is already present in that cell's row set, column set, or box set — if so, the board is invalid. Otherwise add the digit to all three sets and move on.
def is_valid_sudoku(board: list[list[str]]) -> bool:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
val = board[r][c]
if val == ".":
continue
b = (r // 3) * 3 + (c // 3)
if val in rows[r] or val in cols[c] or val in boxes[b]:
return False
rows[r].add(val)
cols[c].add(val)
boxes[b].add(val)
return True
Complexity: The board size is fixed at 9x9, so this is O(1) in
the strict sense, but expressed in terms of board dimension n (here
n = 9) it is O(n^2) time and O(n^2) space, since we visit each of
the n^2 cells once and store up to n digits per row/column/box set.
Share this question