LeetCode 36 - Valid Sudoku

This problem asks us to validate whether a partially filled Sudoku board follows the core Sudoku rules. The board is always a fixed 9 x 9 grid, and each cell contains either a digit from '1' to '9' or the character '.', which represents an empty cell.

leetcodemediumarrayhash-tablematrix

LeetCode Problem 36

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Matrix

Solution

Problem Understanding

This problem asks us to validate whether a partially filled Sudoku board follows the core Sudoku rules. The board is always a fixed 9 x 9 grid, and each cell contains either a digit from '1' to '9' or the character '.', which represents an empty cell.

A valid Sudoku configuration must satisfy three independent conditions:

  1. Every row must contain unique digits from 1 to 9.
  2. Every column must contain unique digits from 1 to 9.
  3. Every 3 x 3 sub-box must contain unique digits from 1 to 9.

The important detail is that we are only validating the current board state. We are not asked to solve the Sudoku puzzle. A board may be incomplete and still be considered valid as long as no Sudoku rule has already been violated.

The input is a two-dimensional array where board[i][j] represents the value at row i and column j. The output is a boolean:

  • true if the current board satisfies all Sudoku constraints
  • false if any duplicate digit appears in a row, column, or sub-box

The constraints are small and fixed:

  • The board is always 9 x 9
  • Every cell contains either '.' or a digit '1' through '9'

Because the input size never changes, the problem is not about handling large-scale data efficiently. Instead, the challenge is implementing the validation logic correctly and cleanly.

Several edge cases are important:

  • Empty cells '.' must be ignored completely.
  • A duplicate may appear in a row, column, or sub-box independently.
  • The same digit may appear multiple times globally as long as they are not in the same row, column, or sub-box.
  • A board can be incomplete and still valid.
  • The duplicate could occur very early or very late in traversal, so the algorithm should detect violations immediately.

Approaches

Brute Force Approach

The brute-force approach checks every row, every column, and every 3 x 3 sub-box independently.

For each row, we scan all nine cells and verify that no digit appears more than once. We repeat the same process for all columns. Then we separately scan each 3 x 3 box and again check for duplicates.

This approach is correct because Sudoku validity is entirely determined by those three conditions. If every row, column, and sub-box contains unique digits, then the board is valid.

A naive implementation may repeatedly scan structures or compare every pair of elements, leading to unnecessary repeated work. For example, checking duplicates with nested loops inside every row or box creates redundant comparisons.

Even though the board size is small and fixed, this style of implementation becomes verbose and harder to reason about.

Optimal Approach

The key insight is that Sudoku validity can be verified during a single traversal of the board.

As we visit each cell, we simultaneously track:

  • Which digits have appeared in each row
  • Which digits have appeared in each column
  • Which digits have appeared in each 3 x 3 sub-box

Hash sets are ideal here because they provide constant-time insertion and lookup.

When we encounter a digit:

  • If it already exists in the corresponding row set, the board is invalid.
  • If it already exists in the corresponding column set, the board is invalid.
  • If it already exists in the corresponding sub-box set, the board is invalid.

Otherwise, we insert the digit into all three structures and continue.

The sub-box index can be computed using:

box_index = (row // 3) * 3 + (col // 3)

This maps the nine 3 x 3 boxes into indices 0 through 8.

This solution is cleaner, easier to maintain, and performs all validation in one pass.

Approach Time Complexity Space Complexity Notes
Brute Force O(9³) O(1) Separately scans rows, columns, and boxes with repeated comparisons
Optimal O(9²) O(1) Single traversal using hash sets for fast duplicate detection

Although we write O(9²) and O(1), the board size is fixed, so both are technically constant time and constant space in practice.

Algorithm Walkthrough

  1. Create three collections to track used digits:
  • One for rows
  • One for columns
  • One for 3 x 3 sub-boxes

Each collection contains nine hash sets, one set per structure. 2. Traverse every cell in the board using nested loops.

The outer loop iterates through rows, and the inner loop iterates through columns. 3. Skip empty cells.

If the current value is '.', it does not participate in Sudoku validation, so continue to the next cell. 4. Compute the sub-box index.

Use:

box_index = (row // 3) * 3 + (col // 3)

This converts the board coordinates into one of the nine sub-box identifiers. 5. Check whether the digit already exists in:

  • The current row set
  • The current column set
  • The current box set

If the digit exists in any of them, return False immediately because a Sudoku rule has been violated. 6. Insert the digit into all three sets.

This records that the digit has now appeared in the current row, column, and box. 7. Continue until all cells have been processed. 8. If no duplicates were found, return True.

Why it works

The algorithm maintains the invariant that every processed row, column, and sub-box contains only unique digits.

Each digit is checked before insertion. Therefore, if a duplicate ever exists, the algorithm detects it immediately. If traversal completes successfully, then no row, column, or sub-box contains repeated digits, which exactly matches the Sudoku validity definition.

Python Solution

from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for row in range(9):
            for col in range(9):
                value = board[row][col]

                if value == ".":
                    continue

                box_index = (row // 3) * 3 + (col // 3)

                if value in rows[row]:
                    return False

                if value in cols[col]:
                    return False

                if value in boxes[box_index]:
                    return False

                rows[row].add(value)
                cols[col].add(value)
                boxes[box_index].add(value)

        return True

The implementation starts by creating three arrays of sets. Each set stores the digits already seen in a particular row, column, or sub-box.

The nested loops iterate through every board position. Empty cells are ignored because they do not affect Sudoku validity.

For non-empty cells, we compute the corresponding sub-box index. The formula groups rows and columns into 3 x 3 regions.

Before inserting the digit, we check whether it already exists in any relevant set. If it does, the board violates Sudoku rules, so the function immediately returns False.

If no duplicate is found, the digit is inserted into all three tracking sets.

After processing the entire board without detecting any conflict, the board is valid, so the function returns True.

Go Solution

func isValidSudoku(board [][]byte) bool {
    rows := make([]map[byte]bool, 9)
    cols := make([]map[byte]bool, 9)
    boxes := make([]map[byte]bool, 9)

    for i := 0; i < 9; i++ {
        rows[i] = make(map[byte]bool)
        cols[i] = make(map[byte]bool)
        boxes[i] = make(map[byte]bool)
    }

    for row := 0; row < 9; row++ {
        for col := 0; col < 9; col++ {
            value := board[row][col]

            if value == '.' {
                continue
            }

            boxIndex := (row/3)*3 + (col / 3)

            if rows[row][value] {
                return false
            }

            if cols[col][value] {
                return false
            }

            if boxes[boxIndex][value] {
                return false
            }

            rows[row][value] = true
            cols[col][value] = true
            boxes[boxIndex][value] = true
        }
    }

    return true
}

The Go solution follows the same logic as the Python version. Since Go does not have a built-in set type, maps with boolean values are used to simulate sets.

Each map tracks whether a digit has already appeared. Accessing a missing key in a Go map returns the zero value false, which makes membership checks straightforward.

The board uses [][]byte instead of strings, so comparisons are performed using byte literals such as '.'.

Worked Examples

Example 1

Input:

[
["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"]
]

We begin scanning from the top-left corner.

Cell Value Row Set Column Set Box Set Result
(0,0) 5 {} {} {} Insert 5
(0,1) 3 {5} {} {5} Insert 3
(0,2) . skip skip skip Continue
(0,4) 7 {5,3} {} {} Insert 7

As traversal continues:

  • No row receives duplicate digits.
  • No column receives duplicate digits.
  • No 3 x 3 box receives duplicate digits.

The algorithm reaches the end and returns:

True

Example 2

Input:

[
["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"]
]

The first important conflict appears here:

Cell Value Box Index Existing Box Values Result
(0,0) 8 0 {} Insert 8
(2,2) 8 0 {8,3,6,9} Duplicate found

Both 8 values belong to the same top-left 3 x 3 box.

As soon as the second 8 is encountered, the algorithm returns:

False

Complexity Analysis

Measure Complexity Explanation
Time O(9²) Every cell is visited once
Space O(1) The board size is fixed, so storage never grows beyond constant size

The algorithm processes exactly 81 cells, and each lookup or insertion into a hash set is constant time on average.

The extra space comes from storing row, column, and box sets. Since there are at most 81 stored digits total, the memory usage is bounded by a constant.

Test Cases

from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for row in range(9):
            for col in range(9):
                value = board[row][col]

                if value == ".":
                    continue

                box_index = (row // 3) * 3 + (col // 3)

                if (
                    value in rows[row]
                    or value in cols[col]
                    or value in boxes[box_index]
                ):
                    return False

                rows[row].add(value)
                cols[col].add(value)
                boxes[box_index].add(value)

        return True

solution = Solution()

# Example 1, valid Sudoku board
board1 = [
    ["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"]
]
assert solution.isValidSudoku(board1) is True  # valid board

# Example 2, duplicate in sub-box
board2 = [
    ["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"]
]
assert solution.isValidSudoku(board2) is False  # duplicate in box

# Duplicate in a row
board3 = [
    ["5","3","5",".","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"]
]
assert solution.isValidSudoku(board3) is False  # duplicate in row

# Duplicate in a column
board4 = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    ["5","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
assert solution.isValidSudoku(board4) is False  # duplicate in column

# Completely empty board
board5 = [["." for _ in range(9)] for _ in range(9)]
assert solution.isValidSudoku(board5) is True  # empty board is valid

# Single filled cell
board6 = [["." for _ in range(9)] for _ in range(9)]
board6[4][4] = "7"
assert solution.isValidSudoku(board6) is True  # minimal valid board
Test Why
Valid example board Confirms correct handling of normal valid input
Duplicate in sub-box Verifies box validation logic
Duplicate in row Verifies row duplicate detection
Duplicate in column Verifies column duplicate detection
Empty board Ensures empty cells are ignored correctly
Single filled cell Confirms minimal valid configuration works

Edge Cases

One important edge case is a completely empty board. Since all cells contain '.', there are no rule violations. A buggy implementation might mistakenly treat missing values as duplicates or invalid input. This solution skips empty cells entirely, so an empty board is correctly considered valid.

Another important edge case is when a duplicate appears only inside a 3 x 3 sub-box while rows and columns remain valid. This is easy to miss if the implementation only validates rows and columns. The dedicated boxes tracking structure ensures sub-box violations are detected independently.

A subtle edge case occurs when the duplicate appears late in traversal. For example, the first eight rows may be completely valid, and the violation may occur in the final cell. The algorithm handles this correctly because every insertion is checked immediately before being recorded.

Another potential source of bugs is incorrect sub-box indexing. If the mapping formula is wrong, cells may be assigned to incorrect boxes. Using:

(row // 3) * 3 + (col // 3)

correctly maps each cell into one of the nine sub-boxes. This guarantees that every 3 x 3 region is validated independently.