Valid Sudoku

LeetCode 36: Valid Sudoku Solution & Explanation

Problem Overview

TL;DR: Scan every filled cell once while using separate existence checks for its row, column, and 3x3 box; return false immediately when any digit has already been seen.

LeetCode 36, Valid Sudoku, asks whether the filled entries in a 9x9 Sudoku board obey three rules:

• A digit cannot appear twice in the same row.
• A digit cannot appear twice in the same column.
• A digit cannot appear twice in the same 3x3 subgrid.

Empty cells represented by "." are ignored. The board does not need to be complete or solvable; only the currently filled values must be valid. This is a popular interview question because it tests matrix traversal, hashing, and constraint tracking.

Brute Force Approach for Valid Sudoku

A direct brute force solution can examine each filled cell and independently scan:

1. The cell's entire row for another occurrence of the same digit.
2. The cell's entire column for another occurrence.
3. The cell's 3x3 subgrid for another occurrence.

Naive Pseudocode

for each cell (row, column):
    if the cell is empty:
        continue

    digit = board[row][column]

    scan all cells in row:
        if the same digit appears elsewhere:
            return false

    scan all cells in column:
        if the same digit appears elsewhere:
            return false

    scan the cell's 3x3 subgrid:
        if the same digit appears elsewhere:
            return false

return true

Complexity

For a general n x n Sudoku-style board, this approach scans up to O(n) cells for each of O(n²) board positions:

• Time: O(n³)
• Space: O(1)

For the fixed 9x9 constraints in LeetCode 36, this is technically bounded by a small constant and will usually pass. Therefore, it does not genuinely fail with Time Limit Exceeded on the given input size. However, it repeatedly scans the same rows, columns, and boxes and does not scale well if the board size is generalized.

The better approach records whether a digit has already appeared, reducing repeated work to a single pass.

Algorithm Strategy: Array/Matrix Manipulation Patterns

Use three groups of existence trackers:

• rows[row][digit] or rows[row]
• columns[column][digit] or columns[column]
• boxes[box][digit] or boxes[box]

The C++ implementation uses fixed-size boolean arrays because the board contains only nine possible digits. The Java and Python implementations use hash sets to store the values already observed.

For every cell:

• Skip ".".
• Compute the numeric digit or retain the string value.
• Compute its 3x3 box index.
• Check all three corresponding trackers.
• Return false if any tracker already contains the value.
• Insert the value into all three trackers.

The scan stops as soon as a duplicate is detected.

Execution Flow

1. Initialize nine row trackers, nine column trackers, and nine box trackers.
2. Start at row 0, column 0.
3. If the cell is ".", skip it.
4. For a filled cell:
   • Read its digit.
   • Calculate box = (row / 3) * 3 + (column / 3).
5. Check the digit against:
   • The current row tracker.
   • The current column tracker.
   • The current box tracker.
6. If the digit is already present in any tracker, return false.
7. Otherwise, insert the digit into all three trackers.
8. Continue through the remaining cells.
9. If all 81 cells are processed without a duplicate, return true.

For example, if a second '4' appears in the upper-left 3x3 box, the box tracker for index 0 already contains '4'. The algorithm detects this during the membership check and returns false immediately.

Proof of Correctness

We prove that the algorithm returns true exactly when the board satisfies all Sudoku uniqueness rules.

If the Algorithm Returns false

The algorithm returns false only when the current digit already exists in at least one of:

• The current row tracker.
• The current column tracker.
• The current box tracker.

By the invariant, each tracker contains exactly the previously encountered digits in that region. Therefore, the current digit is duplicated in that row, column, or box. The board violates a Sudoku rule, so returning false is correct.

If the Algorithm Returns true

The algorithm returns true only after processing every cell without finding a duplicate. For every filled cell, its digit was absent from the corresponding row, column, and box trackers before insertion. Therefore, no row, column, or 3x3 box contains the same digit more than once.

Thus, the board satisfies all required constraints, so returning true is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 202: Happy Number — Store previously seen numbers to detect a repeated state and identify a cycle.
• LeetCode 349: Intersection of Two Arrays — Use a set to test whether values from one array exist in another.
• LeetCode 219: Contains Duplicate II — Track previously seen values while enforcing a distance constraint.
• LeetCode 3: Longest Substring Without Repeating Characters — Maintain a set or map of active characters and detect repeated values during a scan.

In each case, hashing converts repeated-value detection into a direct existence check while the algorithm maintains the state required by the problem's constraints.

Reference Implementation

C++ Solution for LeetCode 36

1class Solution {
2public:
3    bool isValidSudoku(std::vector<std::vector<std::string>>& board) {
4        bool rows[9][10] = {};
5        bool columns[9][10] = {};
6        bool boxes[9][10] = {};
7
8        for (int row = 0; row < 9; ++row) {
9            for (int column = 0; column < 9; ++column) {
10                if (board[row][column] == ".") {
11                    continue;
12                }
13
14                int digit = board[row][column][0] - '0';
15                int box = (row / 3) * 3 + (column / 3);
16
17                if (rows[row][digit] || columns[column][digit] || boxes[box][digit]) {
18                    return false;
19                }
20
21                rows[row][digit] = true;
22                columns[column][digit] = true;
23                boxes[box][digit] = true;
24            }
25        }
26
27        return true;
28    }
29};

The boolean arrays use the digit itself as an index. Index 0 remains unused, while indices 1 through 9 represent the Sudoku digits.

Java Solution for LeetCode 36

1class Solution {
2    public boolean isValidSudoku(String[][] board) {
3        HashSet<String>[] rows = new HashSet[9];
4        HashSet<String>[] columns = new HashSet[9];
5        HashSet<String>[] boxes = new HashSet[9];
6
7        for (int i = 0; i < 9; i++) {
8            rows[i] = new HashSet<>();
9            columns[i] = new HashSet<>();
10            boxes[i] = new HashSet<>();
11        }
12
13        for (int row = 0; row < 9; row++) {
14            for (int column = 0; column < 9; column++) {
15                String value = board[row][column];
16                if (".".equals(value)) {
17                    continue;
18                }
19
20                int box = (row / 3) * 3 + column / 3;
21                if (rows[row].contains(value)
22                        || columns[column].contains(value)
23                        || boxes[box].contains(value)) {
24                    return false;
25                }
26
27                rows[row].add(value);
28                columns[column].add(value);
29                boxes[box].add(value);
30            }
31        }
32
33        return true;
34    }
35}

Each HashSet stores the non-empty values already encountered in one row, column, or box. The contains checks implement the previously seen existence check.

Python Solution for LeetCode 36

1class Solution:
2    def isValidSudoku(self, board: List[List[str]]) -> bool:
3        rows = [set() for _ in range(9)]
4        columns = [set() for _ in range(9)]
5        boxes = [set() for _ in range(9)]
6
7        for row in range(9):
8            for column in range(9):
9                value = board[row][column]
10                if value == ".":
11                    continue
12
13                box = (row // 3) * 3 + column // 3
14                if (value in rows[row] or
15                        value in columns[column] or
16                        value in boxes[box]):
17                    return False
18
19                rows[row].add(value)
20                columns[column].add(value)
21                boxes[box].add(value)
22
23        return True

Python sets provide the required membership test and insertion operations. The row, column, and box state transitions mirror the C++ and Java implementations.