36. Valid Sudoku
Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 50.8%
Problem Breakdown
We are given a fixed-size grid representing a Sudoku board. The goal is to validate if the currently filled cells adhere to standard Sudoku rules: no duplicate digits in any row, column, or sub-box. Empty cells (represented by '.') do not contribute to validity checks and are effectively ignored during validation.
Inputs: A list of lists (List[List[str]]), where each inner list has length 9 containing characters ‘1’-‘9’ or ’.’.
Output: Boolean True if valid, False otherwise.
Implicit Constraints: The board is always . We do not need to solve the puzzle (fill empty cells) nor check for solvability; we only validate existing numbers against duplicates within their specific row/column/box scope.
Intuition
A naive approach would be to iterate through every cell, and for each filled number, scan its entire corresponding row, column, and sub-box to find duplicates. While the grid is small ( cells), scanning repeatedly makes this or worse depending on implementation (where ).
The key insight here is that we only care about uniqueness. We don’t need to store positions, just whether a number has been seen in the current row/column/box. This screams Hash Set usage for lookups and insertions. Since there are 9 rows, 9 columns, and exactly 9 sub-boxes (which can be indexed linearly from 0 to 8), we can maintain three separate collections of sets: one tracking seen numbers per row index, one per column index, and one per box index.
Approach
- Initialize data structures for state tracking:
rows(list of 9 sets),cols(list of 9 sets), andboxes(list of 9 sets). Using lists allows us to map the current row/col/block directly without complex hashing logic during iteration. - Iterate through every cell
(i, j)in the board using nested loops from to . - If a cell contains
'.', skip it (it doesn’t violate rules). - For valid digits:
- Check if digit exists in
rows[i]. If yes -> returnFalseimmediately. Else add to set. - Check if digit exists in
cols[j]. If yes -> returnFalse. Else add to set. - Determine the box index using integer division logic:
(i // 3) * 3 + (j // 3)maps a cell’s block position to an ID . Check existence inboxes[box_id]and update if valid.
- Check if digit exists in
- If loops complete without returning
False, returnTrue.
Complexity Analysis
- Time: relative to the fixed grid size (). In general terms for an board, it is . We visit each cell once; set operations are amortized . Since constraints fix , this effectively runs in constant time.
- Space: because the maximum number of elements stored across all sets is bounded by 81 (total cells). Specifically, we store at most one instance per unique digit for each row/col/box category simultaneously, which is a fixed upper bound regardless of input content distribution within constraints.
Solution
class Solution:
def isValidSudoku(self, board: List[str]) -> bool:
# Initialize sets to track seen numbers in rows, columns, and 3x3 boxes
row_sets = [set() for _ in range(9)]
col_sets = [set() for _ in range(9)]
box_sets = [set() for _ in range(9)]
# Iterate through each cell of the board
for i in range(9):
for j in range(9):
val = board[i][j]
# Skip empty cells as they don't affect validity rules
if val == '.':
continue
# Calculate box index: (row_block_index * 3) + col_block_index
# This maps the top-left to bottom-right blocks linearly from 0-8
box_idx = (i // 3) * 3 + (j // 3)
# Check for duplicates in row, column, and corresponding sub-box
if val in row_sets[i] or \
val in col_sets[j] or \
val in box_sets[box_idx]:
return False
# Add the digit to all three tracking sets
row_sets[i].add(val)
col_sets[j].add(val)
box_sets[box_idx].add(val)
return True
Edge Cases Handled
- Empty Cells: The code explicitly skips
'.'characters, ensuring they do not trigger false positives for duplicates. - Immediate Duplicates: If a duplicate is found in any scope (row/col/box), the function returns
Falseimmediately without processing remaining cells, optimizing performance on invalid inputs. - Box Indexing Logic: The formula
(i // 3) * 3 + (j // 3)correctly maps every cell to one of exactly nine unique box identifiers ( through ), ensuring no cross-contamination between sub-boxes during validation.