36. Valid Sudoku - Detailed Explanation
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.
- Input:
-
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).
- Input:
-
Example 3:
- Input:
board = [ [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."], [".",".",".",".",".",".",".",".","."] ] - Output:
true - Explanation: An empty board is considered valid as there are no conflicting entries.
- Input:
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
Brute Force Code in 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
Optimal Code in 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.
GET YOUR FREE
Coding Questions Catalog
