LeetEye LeetEye
Easy Hash Set / Hash Map ~5 min

Valid Sudoku

arrays-and-hashing valid-sudoku

Problem

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition
2. Each column must contain the digits 1-9 without repetition
3. Each of the nine 3 x 3 sub-boxes must contain the digits 1-9 without repetition

Note: A Sudoku board (partially filled) could be valid but not necessarily solvable. Only validate filled cells.

Examples

Example 1
Input: board =
Output: true
Example 2
Input: board =
Output: false
The first column has two 8s
Key Insight

For each constraint, use a hash set to track seen digits.

Valid Sudoku = no duplicates in any row, column, or 3×3 box. Use sets for each, compute box index with (r//3)*3 + (c//3).

How to Approach This Problem

Pattern Recognition: When you see keywords like valid sudoku arrays-and-hashing, think Hash Set / Hash Map.

Step-by-Step Reasoning

1 How many different duplicate checks does valid Sudoku require?
Answer: 27 (9 rows + 9 columns + 9 boxes)
Each row (9), each column (9), each 3×3 box (9) must have no duplicates = 27 separate checks.
2 For each row/column/box, what operation detects invalidity?
Answer: Checking if any digit appears more than once
We only need to check filled cells. A partial board might not have all digits, but no digit should repeat.
3 Best structure to check for duplicates as you scan?
Answer: Both A and B work
Both work for O(1) lookup. Array is slightly more efficient for fixed range 1-9, but hash set is more general.
4 Cell (5, 7) belongs to which 3×3 box?
Answer: Box 5
row=5, col=7. Box = (5//3)*3 + (7//3) = 1*3 + 2 = 5
5 Return false immediately when:
Answer: A digit is already in the set for its row, column, OR box
Any single duplicate (in any row, column, or box) makes the board invalid. Empty cells ('.') are allowed.
6 Can we check all constraints in a single pass through the board?
Answer: Yes, update row, column, and box sets simultaneously
For each cell, we know its row index, column index, and can compute box index. Update all three sets at once.

Solution

def isValidSudoku(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):
            if board[r][c] == '.':
                continue
            
            num = board[r][c]
            box_idx = (r // 3) * 3 + (c // 3)
            
            if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
                return False
            
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_idx].add(num)
    
    return True

Complexity Analysis

Time O(81)
Space O(81)

Master This Pattern

Build intuition with interactive MCQs. Practice Hash Set / Hash Map problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye