Valid Sudoku
Problem Description
Question
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: board
0
1
2
3
4
5
6
7
8
0
5
3
.
.
7
.
.
.
.
1
6
.
.
1
9
5
.
.
.
2
.
9
8
.
.
.
.
6
.
3
8
.
.
.
6
.
.
.
3
4
4
.
.
8
.
3
.
.
1
5
7
.
.
.
2
.
.
.
6
6
.
6
.
.
.
.
2
8
.
7
.
.
.
4
1
9
.
.
5
8
.
.
.
.
8
.
.
7
9
Output: true
Example 2:
Input: board
0
1
2
3
4
5
6
7
8
0
8
3
.
.
7
.
.
.
.
1
6
.
.
1
9
5
.
.
.
2
.
9
8
.
.
.
.
6
.
3
8
.
.
.
6
.
.
.
3
4
4
.
.
8
.
3
.
.
1
5
7
.
.
.
2
.
.
.
6
6
.
6
.
.
.
.
2
8
.
7
.
.
.
4
1
9
.
.
5
8
.
.
.
.
8
.
.
7
9
Output: false
Explanation: 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 == 9board[i].length == 9board[i][j]is a digit1-9or'.'.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The Brute Force approach involves checking all rows, columns, and sub-grids (3x3) to ensure they contain unique numbers. This is straightforward but can be inefficient due to repeated checks.
Steps:
- Check each row to make sure there are no repeated numbers.
- Check each column and ensure no duplicates.
- Check each 3x3 sub-grid.
Code:
Complexity Analysis
- Time Complexity: O(9^2) = O(81). Each row, column, and grid is checked separately.
- Space Complexity: O(1) for each row and O(9) for columns and blocks used by boolean arrays.
2. Optimized Approach Using HashSet
Intuition:
To optimize, use a HashSet for keeping track of seen numbers efficiently. We iterate once through the board, and at each step, we ensure that no number appears twice in its row, column or sub-grid.
Steps:
- A single loop performs checks using HashSet for:
- Rows
- Columns
- 3x3 sub-grids
- For each filled cell, create unique keys for HashSets.
Code:
Complexity Analysis
- Time Complexity: O(1). We are processing a constant number of cells in a 9x9 grid.
- Space Complexity: O(1). The size of the HashSet used will hold at most 81 elements given all cells are filled without repetition.