36. Valid Sudoku
Problem
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-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without 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:
Example 2:
Constraints:
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or '.'.
Approach
Basically, we want to check if there are duplicates in each row, column and subbox.
To check for duplicates, we can write a helper function that will use a hashmap technique to check for duplicates.
Checking rows and columns is straightforward, the complexity arises with checking the subboxes because we need to figure out how to iterate over them. To keep it simple, we can do 4 nested loops, the box row, the box column, the inner row, the inner column, then we can index the board with board[3 * box_row + row][3 * box_col + col]. Using this, we can create the array of values for the subbox and check for duplicates.
Complexity
Time: O(n)
Since we iterate over the rows, columns and subboxes separately, it's all O(n)
Space: O(n)
The only extra space we create is for the rows, columns and subboxes which all have size of 9. Technically, it's all constant but we'll give it O(n)