Valid Sudoku
Medium
0 views
Topics:
ArraysStrings
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 = [["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
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: 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'.'.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- Can the input board contain characters other than digits 1-9 and '.' (representing empty cells)?
- Is it guaranteed that the input board will always be a 9x9 grid, or could the dimensions vary?
- Are there any constraints on the number of filled cells in the Sudoku board?
- By 'valid,' do you mean that the board could potentially be completed into a fully solved Sudoku puzzle, or just that the current state doesn't violate any Sudoku rules?
- Should I validate that each digit, 1-9, appears at least once in each row, column, and 3x3 subgrid, or is simply no repetition sufficient?
Brute Force Solution
Approach
To check if a Sudoku puzzle is valid using the brute force approach, we'll examine all the rules to see if any are broken. We'll methodically go through each row, column, and 3x3 square, checking for duplicates.
Here's how the algorithm would work step-by-step:
- First, look at the first row of the Sudoku grid.
- Check if there are any repeated numbers in that row. If you find one, the Sudoku is invalid.
- Repeat this process for every row in the grid.
- Next, look at the first column of the Sudoku grid.
- Check if there are any repeated numbers in that column. If you find one, the Sudoku is invalid.
- Repeat this process for every column in the grid.
- Now, divide the Sudoku grid into nine 3x3 squares.
- Look at the first 3x3 square (top-left).
- Check if there are any repeated numbers in that square. If you find one, the Sudoku is invalid.
- Repeat this process for every 3x3 square in the grid.
- If you've checked all the rows, columns, and 3x3 squares, and haven't found any repeated numbers, then the Sudoku is valid.
Code Implementation
def is_valid_sudoku(board):
# Check rows for duplicates
for row in board:
if not is_valid_unit(row):
return False
# Check columns for duplicates
for column_index in range(9):
column = [board[row_index][column_index] for row_index in range(9)]
if not is_valid_unit(column):
return False
# Check 3x3 sub-boxes for duplicates
for box_row in range(3):
for box_column in range(3):
# Extract the 3x3 sub-box
sub_box = [
board[row_index][column_index]
for row_index in range(box_row * 3, box_row * 3 + 3)
for column_index in range(box_column * 3, box_column * 3 + 3)
]
if not is_valid_unit(sub_box):
return False
return True
def is_valid_unit(unit):
seen = set()
# Only check for 1-9.
for number in unit:
if number != '.':
if number in seen:
# Duplicates are not allowed
return False
# Record that we have seen this number
seen.add(number)
return TrueBig(O) Analysis
Time Complexity
O(1) – The input is a 9x9 Sudoku grid, meaning the input size is fixed. We iterate through rows, columns, and 3x3 subgrids, each with a constant size. The number of operations performed is therefore bounded by a constant, regardless of the specific numbers within the Sudoku grid. Thus, the time complexity is O(1) as it does not scale with a variable input size.
Space Complexity
O(1) – The provided algorithm checks for duplicates in rows, columns, and 3x3 subgrids of a Sudoku board. To perform duplicate checking, temporary sets or similar data structures are implicitly used within each row, column, and subgrid check. However, since Sudoku boards have fixed dimensions (9x9), the maximum size of these temporary sets is bounded by a constant (9). Thus, the space used for these checks does not scale with the size of a potentially larger Sudoku grid, remaining constant. Therefore, the auxiliary space complexity is O(1).
Optimal Solution
Approach
The puzzle is valid if each row, column, and 3x3 square contains the digits 1-9 without repetition. Instead of checking each row, column, and square separately, we will check them all at the same time to avoid repeating work.
Here's how the algorithm would work step-by-step:
- For each number, we'll check three things: the row it's in, the column it's in, and the 3x3 box it's in.
- We need a way to remember if we've seen a number in a row, column, or box. Think of using separate notebooks for rows, columns, and boxes.
- Go through each cell of the puzzle. If you see a number, check if it's already in the notebook for that row, column, or box. If it is, the puzzle is invalid.
- If the number is not in the notebooks, mark it down in all three notebooks (row, column, and box) so you know you've seen it.
- Keep going until you've checked every cell. If you never found a duplicate in any of the notebooks, then the Sudoku puzzle is valid.
Code Implementation
def isValidSudoku(board):
row_values = [{} for _ in range(9)]
column_values = [{} for _ in range(9)]
box_values = [{} for _ in range(9)]
for row_index in range(9):
for column_index in range(9):
current_number = board[row_index][column_index]
if current_number != '.':
current_number = int(current_number)
# Box index is derived from row and column
box_index = (row_index // 3) * 3 + column_index // 3
# Check row
if current_number in row_values[row_index]:
return False
row_values[row_index][current_number] = 1
# Check column
if current_number in column_values[column_index]:
return False
column_values[column_index][current_number] = 1
# Check box
if current_number in box_values[box_index]:
return False
box_values[box_index][current_number] = 1
return TrueBig(O) Analysis
Time Complexity
O(1) – The algorithm iterates through each cell of the Sudoku board exactly once. The size of the Sudoku board is fixed at 9x9, so it always has 81 cells. Thus, the number of operations performed is constant, regardless of the input values. Therefore, the time complexity is O(1).
Space Complexity
O(1) – The provided explanation mentions using 'notebooks' to track seen numbers for rows, columns, and boxes. Since a Sudoku board has a fixed size (9x9), we will have 9 notebooks each for rows, columns, and boxes. Each notebook stores the presence of numbers from 1 to 9. Therefore, the space required for these notebooks is constant regardless of the specific numbers in the Sudoku board. The auxiliary space is independent of the input size and is therefore O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty board | Return true immediately as an empty board is considered trivially valid. |
| Board with non-digit characters (other than '.') | Check if each character is either a digit '1'-'9' or '.' and return false if not. |
| Board with digits outside the range '1'-'9' | Explicitly check that the digits are within the valid range '1'-'9' if not '.'. |
| Repetition of digits in a row | Use a set or similar data structure to track digits in each row and return false if a duplicate is found. |
| Repetition of digits in a column | Use a set or similar data structure to track digits in each column and return false if a duplicate is found. |
| Repetition of digits in a 3x3 sub-box | Use a set or similar data structure to track digits in each 3x3 sub-box and return false if a duplicate is found. |
| Board that is not 9x9 | Verify that the board is 9x9 and return false if it's not. |
| Input contains leading zeros | While technically a character, treat the presence of '0' similarly to other invalid chars and return false. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
