#36

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Valid Sudoku

Check if a 9x9 Sudoku board is valid by scanning rows, columns, and sub-boxes with hash lookups, ensuring no duplicates exist.

array hash table matrix

Problem Statement

You are given a 9x9 Sudoku board partially filled with digits 1-9 and empty cells represented by '.'. Your task is to determine whether the current state of the board is valid according to Sudoku rules. Only filled cells must follow the rules, so you do not need to check whether the board is solvable or complete.

A valid board requires that each digit appears at most once per row, column, and each of the nine 3x3 sub-boxes. Implement an algorithm that efficiently scans the board using arrays and hash tables to detect duplicates. Consider edge cases like repeated digits in rows, columns, or sub-boxes, which invalidate the board immediately.

Examples

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 details omitted.

Example 2

Input: board = [["8","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: false

Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints

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

Solution Approach

Row, Column, and Sub-box Tracking

Use three separate hash sets: one for rows, one for columns, and one for 3x3 sub-boxes. Iterate over each cell in the 9x9 board. If the cell contains a digit, check if it already exists in the corresponding row, column, or sub-box set. If it does, return false immediately. Otherwise, add the digit to all relevant sets. This approach leverages the array scanning plus hash lookup pattern to quickly detect duplicates while ensuring constant-time insertion and lookup in hash sets.

Mapping Cells to Sub-boxes

To efficiently identify the 3x3 sub-box for a given cell, compute the sub-box index using integer division: subBoxIndex = (row / 3) * 3 + (col / 3). This maps each cell to one of the nine sub-boxes. Then, use a hash set for each sub-box to track which digits are already present. By combining this mapping with hash lookups, you avoid scanning all cells within a box repeatedly, ensuring that the algorithm maintains optimal performance for the problem's array scanning plus hash table pattern.

Iterative Validation and Early Exit

Iterate over the board row by row and column by column, performing the duplicate check using the pre-initialized hash sets. Empty cells are skipped to prevent unnecessary processing. If any duplicate is found in a row, column, or sub-box, return false immediately to minimize iterations. Once all cells are scanned without conflicts, return true. This early exit strategy avoids full traversal in invalid cases, preserving efficiency and aligning with the time-space trade-offs inherent to array scanning with hash-based validation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(1) for this problem since the board size is fixed at 9x9, and each cell is processed once. Space complexity is O(1) as well, using fixed-size hash sets for rows, columns, and sub-boxes. This explains why both provided time and space complexities remain constant despite the apparent nested iterations.

What Interviewers Usually Probe

Do you recognize how duplicate checks in rows, columns, and sub-boxes can be optimized using hash sets?
Can you map each board cell to its 3x3 sub-box index without extra loops?
Will you handle empty cells efficiently to avoid unnecessary hash operations?

Common Pitfalls or Variants

Common pitfalls

Confusing the 3x3 sub-box indexing, which can lead to missed duplicates or false positives.
Checking only rows and columns but forgetting sub-boxes, which breaks Sudoku rules.
Attempting to scan sub-boxes with nested loops for every cell instead of using precomputed hash sets, causing redundant computations.

Follow-up variants

Determine the minimum changes required to make a partially filled Sudoku board valid.
Validate a Sudoku board of arbitrary size N x N with sqrt(N) x sqrt(N) sub-boxes.
Implement a Sudoku solver that fills empty cells while maintaining validity at each step.

FAQ

What pattern does the Valid Sudoku problem use?

The problem follows an array scanning plus hash lookup pattern where each row, column, and 3x3 sub-box is scanned and checked with hash sets.

Why do I need separate hash sets for rows, columns, and sub-boxes?

Each dimension must be validated independently; separate hash sets prevent conflicts and allow constant-time duplicate detection within rows, columns, and sub-boxes.

How do I map a cell to its 3x3 sub-box index?

Use integer division: subBoxIndex = (row / 3) * 3 + (col / 3). This uniquely identifies each of the nine 3x3 sub-boxes efficiently.

Can empty cells affect the validation?

No, empty cells represented by '.' are skipped during validation. Only filled cells are inserted into hash sets, avoiding false duplicates.

What is the main failure mode to watch for in this problem?

The primary failure mode is duplicates appearing in any row, column, or sub-box. Missing a sub-box check or miscomputing indices causes false positives or negatives.

terminal

Solution

Solution 1: Traversal once

The valid sudoku satisfies the following three conditions:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        sub = [[False] * 9 for _ in range(9)]
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c == '.':
                    continue
                num = int(c) - 1
                k = i // 3 * 3 + j // 3
                if row[i][num] or col[j][num] or sub[k][num]:
                    return False
                row[i][num] = True
                col[j][num] = True
                sub[k][num] = True
        return True

Continue Practicing

#37 sudoku solver #73 set matrix zeroes #840 magic squares in grid