Valid Sudoku
Problem Statement
You are given a a 9 x 9
Sudoku board board
. A Sudoku board is valid if the following rules are followed:
- Each row must contain the digits
1-9
without duplicates. - Each column must contain the digits
1-9
without duplicates. - Each of the nine
3 x 3
sub-boxes of the grid must contain the digits1-9
without duplicates.
Return true
if the Sudoku board is valid, otherwise return false
Note: A board does not need to be full or be solvable to be valid.
Example 1:
# Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","8",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]]# Output: True
Example 2:
# Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","1",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]]# Output: False# Explanation: There are two 1's in the top-left 3x3 sub-box.
Constraints:
board.length == 9
board[i].length == 9
board[i][j]
is a digit1-9
or'.'
You should aim for a solution as good or better than O(n^2)
time and O(n^2)
space, where n
is the number of rows in the square grid.
Recommended Time and Space Complexity
You should aim for a solution as good or better than O(n^2)
time and O(n^2)
space, where n
is the number of rows in the square grid.
Hint 1
Which data structure would you prefer to use for checking duplicates?
Hint 2
You can use a hash set for every row and column to check duplicates. But how can you efficiently check for the squares?
Hint 3
We can find the index of each square by the equation (row / 3) * 3 + (col / 3)
. Then we use hash set for O(1)
lookups while inserting the number into its row, column and square it belongs to. We use separate hash maps for rows, columns, and squares.
Solution
Brute Force
def is_valid_sudoku(board: list[list[str]]) -> bool: for row in range(9): seen = set() for i in range(9): if board[row][i] == ".": continue if board[row][i] in seen: return False seen.add(board[row][i])
for col in range(9): seen = set() for i in range(9): if board[i][col] == ".": continue if board[i][col] in seen: return False seen.add(board[i][col])
for square in range(9): seen = set() for i in range(3): for j in range(3): row = (square // 3) * 3 + i col = (square % 3) * 3 + j if board[row][col] == ".": continue if board[row][col] in seen: return False seen.add(board[row][col]) return True
Time complexity: O(n^2)
Space complexity: O(n^2)