36. Valid Sudoku - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

Determine if a 9×9 Sudoku board is valid. A valid board must satisfy the following rules:

Each row must contain the digits 1–9 without repetition.
Each column must contain the digits 1–9 without repetition.
Each of the nine 3×3 sub-boxes must contain the digits 1–9 without repetition.

The board can be partially filled, where empty cells are represented by the character '.'. Note that a valid board does not necessarily have to be solvable.

Example Inputs and Outputs:

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
Explanation: Each row, column, and 3×3 sub-box contains no duplicates.

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
Explanation: The digit '8' appears twice in the first column (and also in the first row of the first 3×3 box).

Example 3:

Input:

board = [
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."]
]

Output: true
Explanation: An empty board is considered valid as there are no conflicting entries.

Constraints:

The board is a 9×9 2D array.
Each element is either a digit '1' to '9' or the character '.'.

Hints for Solving the Problem:

Row Check: How can you verify that no row contains duplicate digits (ignoring empty cells)?
Column Check: Similarly, how can you check each column for duplicates?
Sub-box Check: How will you determine which 3×3 sub-box an element belongs to and check for duplicates there?
Single Pass Idea: Can you combine these checks into a single traversal by using a set or dictionary to record seen values with keys representing the row, column, and box constraints?

Approach 1: Brute Force

Idea:

Rows: Iterate over each row and use a set to check for duplicates.
Columns: Iterate over each column (using nested loops) and check for duplicates.
Sub-boxes: For each of the nine 3×3 sub-boxes, iterate over the cells and verify there are no duplicate digits.

Since the board is of fixed size (9×9), this approach is acceptable, even though conceptually it involves multiple passes.

Brute Force Code in Python

Python3

. . . .

Brute Force Code in Java

Java

. . . .

Approach 2: Optimal Single-Pass Using a HashSet

Idea:

Traverse the board once and record seen numbers with keys representing:

The row number and digit (e.g., "row 0 - 5").
The column number and digit (e.g., "col 1 - 3").
The box index and digit (e.g., "box 0 - 8" where box index is computed as (i/3)*3 + j/3).

If any key is repeated, then the board is invalid.

Optimal Code in Python

Python3

. . . .

Optimal Code in Java

Java

. . . .

Complexity Analysis:

Time Complexity:
- Both approaches traverse the 9×9 board. Although each cell is visited once (or a few constant times), the board size is fixed at 81 cells.
- Conceptually, if the board were n×n, the time complexity would be O(n²).
Space Complexity:
- For the brute force approach, extra space is used for sets on each row, column, and sub-box but is O(1) in the context of a 9×9 board.
- The optimal approach uses a hash set with at most 3 × 81 keys, which is also O(1) for a fixed board size.

Edge Cases:

Empty Board: An empty 9×9 board (all cells are '.') is valid.
Single Value Violations: A duplicate digit in any row, column, or sub-box should trigger a false result.
Non-Digit Characters: The board is assumed to contain only digits or '.'.

Common Mistakes:

Incorrect Sub-box Indexing: A common error is not correctly calculating the sub-box index. Use (i / 3, j / 3) to determine the box.
Forgetting to Skip Empty Cells: Ensure that cells with '.' are ignored during duplicate checks.
Multiple Passes Over the Board: While a multiple-pass solution works for a fixed board size, combining the checks into a single pass is more efficient and elegant.

Alternative Variations:

Sudoku Solver: Instead of validating the board, solving the board with backtracking.
Larger Sudoku Boards: Adapting the solution to handle boards of varying sizes (e.g., 16×16) with similar validation rules.

Related Problems for Further Practice:

Sudoku Solver (LeetCode 37): Solve an entire Sudoku board using backtracking.
Word Search (LeetCode 79): Practice grid traversal with constraints.
N-Queens: Another grid-based problem that involves careful row, column, and diagonal tracking.