Valid Sudoku
Medium
1 view
Topics:
Arrays
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:
- Besides digits 1-9 and '.', can the input board contain any other characters?
- Is the input board always a 9x9 grid, or could the dimensions vary?
- Can I assume the '.' character represents an empty cell and should be ignored when checking for duplicates?
- If the board is invalid, should I return false immediately upon detecting an error, or continue checking the rest of the board?
- Are there any specific error messages or exceptions I should raise if the input is malformed (e.g., not a 9x9 array)?
Brute Force Solution
Approach
To solve the Sudoku problem by brute force, we check all possible numbers for each empty spot. We fill in each spot one by one, trying every possible digit from 1 to 9, until a valid or invalid solution is found.
Here's how the algorithm would work step-by-step:
- Go through the Sudoku grid, one spot at a time.
- If a spot is empty, try putting the number 1 in it.
- Check if putting that number makes the Sudoku rules invalid (same number in the row, column, or 3x3 square).
- If it's invalid, try the number 2 instead, and keep going until you find a valid number or run out of numbers.
- If you find a valid number, move to the next empty spot and repeat the process.
- If you run out of valid numbers for a spot, go back to the previous spot and change its number to the next valid one.
- Keep doing this until the entire grid is filled correctly, or until you've tried every possibility and none of them work.
Code Implementation
def is_valid_sudoku(board):
board_size = 9
def is_valid(row_number, column_number, number):
# Check if the number is already present in the row
for i in range(board_size):
if board[row_number][i] == str(number):
return False
# Check if the number is already present in the column
for i in range(board_size):
if board[i][column_number] == str(number):
return False
# Check if the number is already present in the 3x3 sub-grid
subgrid_row_start = (row_number // 3) * 3
subgrid_col_start = (column_number // 3) * 3
for i in range(3):
for j in range(3):
if board[subgrid_row_start + i][subgrid_col_start + j] == str(number):
return False
return True
def solve_sudoku():
for row_number in range(board_size):
for column_number in range(board_size):
if board[row_number][column_number] == '.':
# Try each number from 1 to 9
for number in range(1, 10):
# Check if the current number is valid
if is_valid(row_number, column_number, number):
board[row_number] = board[row_number][:column_number] + str(number) + board[row_number][column_number+1:]
# Recursively try to solve the rest of the Sudoku
if solve_sudoku():
return True
# If the recursive call fails, backtrack
board[row_number] = board[row_number][:column_number] + '.' + board[row_number][column_number+1:]
# No valid number was found, so we need to backtrack
return False
# If no empty cells are left, the Sudoku is solved
return True
return solve_sudoku()
Big(O) Analysis
Time Complexity
O(9^(m)) – The algorithm iterates through each empty cell, of which there can be 'm' in total. For each empty cell, it attempts to fill it with a number from 1 to 9. In the worst-case scenario, the algorithm explores all 9 possibilities for each of the 'm' empty cells before backtracking. Therefore, the time complexity is approximately 9 multiplied by itself 'm' times, leading to O(9^(m)). This exponential complexity arises from the brute-force approach of trying every possible digit in each empty spot.
Space Complexity
O(1) – The provided plain English explanation describes a brute-force Sudoku solver that attempts to fill empty cells one by one. It does *not* explicitly mention the use of any auxiliary data structures like lists, hashmaps, or sets. The algorithm primarily involves backtracking and modifying the input board in place. Although recursion is implied, its depth is bounded by the number of empty cells, which is at most 81. However, since the question asks about the *provided* solution based on the plain English explanation, and the explanation doesn't define any explicit auxiliary data structures, we assume the space complexity is constant because only a few integer/boolean variables are needed to track current position and validity, regardless of the Sudoku grid size (N where N is fixed at 9x9).
Optimal Solution
Approach
The goal is to check if a partially filled Sudoku board follows the rules. The efficient method involves checking each row, column, and 3x3 square only once to see if any numbers are repeated within them.
Here's how the algorithm would work step-by-step:
- Go through each row and check if any number appears more than once. If it does, the Sudoku is invalid.
- Go through each column and do the same thing: check for repeated numbers. If you find any, the Sudoku is invalid.
- Divide the Sudoku board into nine 3x3 squares. Check each square individually for repeated numbers. Again, if you find a repeat, it's invalid.
- If you've checked all rows, columns, and squares without finding any repeats, the Sudoku is valid.
Code Implementation
def is_valid_sudoku(board):
board_size = 9
def has_duplicates(elements):
seen = set()
for element in elements:
if element != '.' and element in seen:
return True
seen.add(element)
return False
# Check each row for duplicates
for row in range(board_size):
if has_duplicates(board[row]):
return False
# Check each column for duplicates
for column in range(board_size):
if has_duplicates([board[row][column] for row in range(board_size)]):
return False
# Check each 3x3 sub-box for duplicates
# Ensures each sub-box has unique values
for box_row in range(0, board_size, 3):
for box_column in range(0, board_size, 3):
elements_in_subgrid = [
board[row][column]
for row in range(box_row, box_row + 3)
for column in range(box_column, box_column + 3)
]
if has_duplicates(elements_in_subgrid):
return False
return TrueBig(O) Analysis
Time Complexity
O(1) – The algorithm iterates through each row, column, and 3x3 subgrid of the Sudoku board. Because the Sudoku board has a fixed size (9x9), the number of operations performed is constant regardless of the numbers present in the board. The number of rows, columns and subgrids are fixed, leading to a fixed number of checks. Therefore, the time complexity is O(1).
Space Complexity
O(1) – The algorithm checks rows, columns, and 3x3 squares for duplicates. To track the numbers seen in each row, column, or square, we can use a set or a similar data structure. Since the Sudoku board has fixed dimensions (9x9), the maximum size of these sets is limited by the number of possible values (1-9), which is constant. Therefore, the space used by these sets is constant regardless of the input, resulting in O(1) space complexity.
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty board input | The code should check for null or empty board input and return true immediately because an empty board satisfies the Sudoku rules vacuously. |
| Board with invalid dimensions (not 9x9) | The code should validate the board dimensions before processing, returning false if it's not a 9x9 matrix. |
| Board containing characters other than digits 1-9 or '.' | The code should validate each cell, returning false if it finds a character outside the allowed set (1-9, .). |
| All cells are empty ('.') | The solution should correctly handle this case, resulting in a valid Sudoku (return true). |
| A single row, column, or box contains duplicate digits | The solution uses sets to detect duplicates within each row, column, and 3x3 sub-box and returns false if found. |
| Board with very large numbers if non-character types were incorrectly used | Since the input is characters '1'-'9', the code does not need to handle integer overflow or large numbers. |
| Board with maximum allowed number of filled cells but still invalid | The sets used for validation still work correctly to detect duplicates even when a very large number of cells are filled (but the board remains invalid). |
| Integer overflow when calculating box index | The box index calculation `(row / 3) * 3 + column / 3` is designed to prevent integer overflow because row, column are in range [0, 8]. |
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
