Domain 2MediumCORE

Valid Sudoku

We are given a fixed-size $9 times 9$ 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 $3 times 3$ sub-box. Empty cells (represented by '.') do not contribute to validity checks and are effectively ignored during validation.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table

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 9×99 \times 9 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 3×33 \times 3 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 9×99 \times 9. 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 (8181 cells), scanning repeatedly makes this O(N3)O(N^3) or worse depending on implementation (where N=9N=9).

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 O(1)O(1) 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

  1. Initialize data structures for state tracking: rows (list of 9 sets), cols (list of 9 sets), and boxes (list of 9 sets). Using lists allows us to map the current row/col/block directly without complex hashing logic during iteration.
  2. Iterate through every cell (i, j) in the board using nested loops from 00 to 88.
  3. If a cell contains '.', skip it (it doesn’t violate rules).
  4. For valid digits:
    • Check if digit exists in rows[i]. If yes -> return False immediately. Else add to set.
    • Check if digit exists in cols[j]. If yes -> return False. 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 0..80..8. Check existence in boxes[box_id] and update if valid.
  5. If loops complete without returning False, return True.

Complexity Analysis

  • Time: O(1)O(1) relative to the fixed grid size (9×99 \times 9). In general terms for an N×NN \times N board, it is O(N2)O(N^2). We visit each cell once; set operations are amortized O(1)O(1). Since constraints fix N=9N=9, this effectively runs in constant time.
  • Space: O(1)O(1) 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 False immediately 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 (00 through 88), ensuring no cross-contamination between sub-boxes during validation.