What pattern does Valid Sudoku use?

The Pattern: Hash Maps (Set Tracking for Uniqueness) The Heuristic: When a problem requires checking for duplicates across multiple independent categories simultaneously, maintain separate hash sets for each category and update them in a single pass to detect conflicts efficiently.

Valid Sudoku — Hash Maps

Q: What is the time complexity of Valid Sudoku?

O(1). The board size is fixed at 9x9, so the algorithm performs a constant number of operations (81 cells), each with O(1) set lookups and insertions.

Problem

Given a 9x9 Sudoku board, determine if it is valid according to Sudoku rules: each row, each column, and each of the nine 3x3 sub-boxes must contain the digits 1-9 without repetition. Empty cells are denoted by '.' and can be ignored.

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

Example

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

The algorithm iterates through each cell, skipping empty cells. For each digit, it checks if the digit has already appeared in the current row, column, or 3x3 sub-box. For example, at row 0, column 0, digit '5' is added to the row 0 set, column 0 set, and sub-box (0,0) set. If a duplicate is found in any of these sets, the board is invalid. Since no duplicates are found, the board is valid.

Approach

Straightforward Solution

A brute-force approach would check each row, column, and sub-box separately for duplicates, possibly scanning multiple times, resulting in redundant work and higher complexity.

Core Observation

Sudoku validity depends on ensuring no digit repeats in any row, column, or 3x3 sub-box. This can be checked by tracking seen digits in these three categories independently.

Path to Optimal

The key recognition signals are 'no duplicate digits in rows, columns, and sub-boxes' and 'fixed 9x9 board size'. These indicate using hash sets (hash maps) to track seen digits efficiently. By iterating once over the board and updating three sets per digit, duplicates can be detected in O(1) time per check, resulting in a single pass O(1) time solution due to fixed board size.

Optimal Approach

Use three hash maps (dictionaries) keyed by row index, column index, and sub-box coordinates to store sets of digits seen so far. For each non-empty cell, check if the digit is already in any of the three sets. If yes, return false immediately. Otherwise, add the digit to all three sets and continue. If no duplicates are found after full iteration, return true.

Time

O(1)

The board size is fixed at 9x9, so the algorithm performs a constant number of operations (81 cells), each with O(1) set lookups and insertions.

Space

O(1)

The auxiliary space is constant because the sets store digits for fixed 9 rows, 9 columns, and 9 sub-boxes, each with at most 9 digits.

Solution

Python

1from collections import defaultdict
2
3class Solution:
  def isValidSudoku(self, board: List[List[str]]) -> bool:
      rows = defaultdict(set)
      cols = defaultdict(set)
      squares = defaultdict(set)
8
      for r in range(9):
          for c in range(9):
              if board[r][c] == ".":
                  continue
              
              num = board[r][c]
              square_key = (r // 3, c // 3)
16
              if (num in rows[r] or
                  num in cols[c] or
                  num in squares[square_key]):
                  return False
              
              rows[r].add(num)
              cols[c].add(num)
              squares[square_key].add(num)
      
      return True

Step-by-Step Solution

1

Track Seen Digits in Rows, Columns, and Sub-boxes Using Hash Sets

5rows = defaultdict(set)
6cols = defaultdict(set)
7squares = defaultdict(set)

Objective

To maintain three separate hash maps that record digits seen so far in each row, column, and 3x3 sub-box.

Key Insight

By using hash maps keyed by row, column, and sub-box indices, each storing a set of digits, the algorithm can instantly check for duplicates in constant time. This structure allows simultaneous tracking of all three constraints in a single pass, avoiding redundant scans and enabling early termination upon detecting invalidity.

Interview Quick-Check

Core Logic

Use three dictionaries mapping row, column, and sub-box indices to sets of digits to track uniqueness constraints simultaneously.

State & Boundaries

Initialize empty sets for each row, column, and sub-box before iteration to ensure clean tracking.

Common Pitfalls & Bugs

Forgetting to compute the correct sub-box key (r // 3, c // 3) can cause incorrect grouping and missed duplicates.

2

Iterate Over Each Cell and Validate Digit Placement

9for r in range(9):
  for c in range(9):
      if board[r][c] == ".":
          continue
      num = board[r][c]
      square_key = (r // 3, c // 3)
      if (num in rows[r] or
          num in cols[c] or
          num in squares[square_key]):
          return False
      rows[r].add(num)
      cols[c].add(num)
      squares[square_key].add(num)

Objective

To scan every cell in the 9x9 board, skip empty cells, and verify that each digit does not violate Sudoku rules by appearing more than once in its row, column, or sub-box.

Key Insight

The iteration covers all cells systematically. For each digit, the algorithm checks all three sets for duplicates before adding the digit. This immediate validation ensures early detection of invalid boards, preventing unnecessary work. The sub-box is identified by integer division of row and column indices by 3, grouping cells into their respective 3x3 boxes.

Interview Quick-Check

Core Logic

For each non-empty cell, check if the digit exists in the corresponding row, column, or sub-box set; if so, return false immediately.

State & Boundaries

Skip cells with '.' since they represent empty cells and do not affect validity.

Common Pitfalls & Bugs

Failing to add the digit to all three sets after validation leads to incorrect duplicate detection in subsequent iterations.

3

Return True After Full Validation Without Conflicts

26	`return True`

Objective

To confirm the board's validity by returning true after all cells have been checked without detecting duplicates.

Key Insight

If the iteration completes without returning false, it means no digit violates Sudoku rules in any row, column, or sub-box. Returning true signals that the board is valid. This final step is the natural conclusion of the single-pass validation.

Interview Quick-Check

Core Logic

Returning true after full iteration confirms no duplicates were found, validating the Sudoku board.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 17 Critical

if (num in rows[r] or

Check if the digit already exists in the current row's set.

This check is the critical validation step that enforces the row uniqueness rule; detecting a duplicate here means the board violates Sudoku constraints and must be rejected.

Line 20 Critical

return False

Return false immediately if any duplicate is found.

Returning false here is the definitive algorithmic move that stops processing as soon as a violation is detected, ensuring correctness and efficiency.

Line 7 Critical

squares = defaultdict(set)

Initialize a dictionary to map each 3x3 sub-box coordinate to a set of seen digits.

Sub-box uniqueness is a key Sudoku rule; grouping cells by integer division of row and column indices creates fixed sub-box keys for efficient tracking.

Line 15 Critical

square_key = (r // 3, c // 3)

Compute the sub-box key by integer dividing row and column indices by 3.

This calculation maps each cell to one of the nine 3x3 sub-boxes, enabling localized duplicate tracking.

Line 18 Critical

num in cols[c] or

Check if the digit already exists in the current column's set.

Column duplicates violate Sudoku rules; this check ensures column uniqueness is maintained.

Line 19 Critical

num in squares[square_key]):

Check if the digit already exists in the current sub-box's set.

Sub-box duplicates are forbidden; this check enforces the third core Sudoku uniqueness constraint.

Line 26 Critical

return True

Return true after validating all cells without detecting duplicates.

Completing the iteration without early termination confirms the board satisfies all Sudoku uniqueness constraints.

Line 5 Core

rows = defaultdict(set)

Initialize a dictionary to map each row index to a set of seen digits.

This data structure enables O(1) average-time checks for duplicates in each row, which is essential for enforcing Sudoku's row uniqueness rule.

Line 6 Core

cols = defaultdict(set)

Initialize a dictionary to map each column index to a set of seen digits.

Tracking digits per column separately allows immediate detection of duplicates in columns, fulfilling the column uniqueness constraint.

Line 22 Core

rows[r].add(num)

Add the digit to the current row's set of seen digits.

Recording the digit in the row set updates the state for future duplicate checks within the same row.

Line 23 Core

cols[c].add(num)

Add the digit to the current column's set of seen digits.

Updating the column set maintains accurate tracking of digits seen in this column for subsequent checks.

Line 24 Core

squares[square_key].add(num)

Add the digit to the current sub-box's set of seen digits.

This update ensures the sub-box set reflects all digits encountered, enabling correct duplicate detection.

Line 11 Core

if board[r][c] == ".":

Check if the current cell is empty ('.').

Empty cells do not affect Sudoku validity and should be skipped to avoid false duplicate detection.

Line 12 Core

continue

Skip processing for empty cells.

Continuing to the next iteration prevents unnecessary checks and maintains correctness by ignoring empty cells.

Line 14 Standard

num = board[r][c]

Retrieve the digit character at the current cell.

Extracting the digit allows subsequent validation against row, column, and sub-box constraints.

Line 9 Standard

for r in range(9):

Start iterating over each row index from 0 to 8.

Systematic traversal of all rows ensures every cell is checked exactly once, covering the entire board.

Line 10 Standard

for c in range(9):

Start iterating over each column index from 0 to 8 within the current row.

Nested iteration over columns completes the full 9x9 grid traversal, enabling per-cell validation.

Test Your Understanding

Why is it necessary to check all three categories (row, column, and sub-box) for duplicates rather than just one or two?

Because Sudoku rules require uniqueness in each row, each column, and each 3x3 sub-box independently; failing to check any one category could allow duplicates that violate the rules, making the board invalid.

Don't just read it. Drill it.

Reconstruct Valid Sudoku from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Start drilling Valid Sudoku for free

1	`from collections import defaultdict`
2
3	`class Solution:`
4	`def isValidSudoku(self, board: List[List[str]]) -> bool:`
5	`rows = defaultdict(set)`
6	`cols = defaultdict(set)`
7	`squares = defaultdict(set)`
8
9	`for r in range(9):`
10	`for c in range(9):`
11	`if board[r][c] == ".":`
12	`continue`
13
14	`num = board[r][c]`
15	`square_key = (r // 3, c // 3)`
16
17	`if (num in rows[r] or`
18	`num in cols[c] or`
19	`num in squares[square_key]):`
20	`return False`
21
22	`rows[r].add(num)`
23	`cols[c].add(num)`
24	`squares[square_key].add(num)`
25
26	`return True`

9	`for r in range(9):`
10	`for c in range(9):`
11	`if board[r][c] == ".":`
12	`continue`
14	`num = board[r][c]`
15	`square_key = (r // 3, c // 3)`
17	`if (num in rows[r] or`
18	`num in cols[c] or`
19	`num in squares[square_key]):`
20	`return False`
22	`rows[r].add(num)`
23	`cols[c].add(num)`
24	`squares[square_key].add(num)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Track Seen Digits in Rows, Columns, and Sub-boxes Using Hash Sets

Iterate Over Each Cell and Validate Digit Placement

Return True After Full Validation Without Conflicts

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.