Valid Sudoku
Asked at Apple
Problem
Determine if a 9x9 Sudoku board is valid according to the rules: each row, column, and 3x3 sub-box must contain digits 1-9 without repetition. The board may be partially filled; you only need to validate the existing entries, not whether it is solvable.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
How to Think About It
Brute force: for each cell, check all cells in the same row, column, and box for duplicates.
Use three hash sets per row, column, and box to track seen digits.
Iterate through all 81 cells once, inserting each digit into the appropriate sets.
For boxes, compute the box index as (row/3)*3 + col/3.
All checks are done in a single pass: O(81) time and O(81) space.
Optimal Approach
Maintain 27 sets: 9 for rows, 9 for columns, and 9 for 3x3 boxes. For each filled cell, check if the digit is already in the corresponding row, column, or box set. If yes, return false. Otherwise, add the digit to all three sets. If all 81 cells pass, return true. This is O(81) time and O(81) space.
What Trips People Up in Real Interviews
Clarify: only filled cells matter; dots are ignored.
Hash sets can be replaced with bitmasks for O(1) extra space.
Be careful with box indexing: (row/3)*3 + col/3 maps each cell to its 3x3 box.
Interviewers may ask to also solve the board — that is a separate backtracking problem.
Confirm whether the input is guaranteed to be a 9x9 board.
Solution Code
class Solution:
def isValidSudoku(self, board: list[list[str]]) -> bool:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
val = board[r][c]
if val == '.':
continue
b = (r // 3) * 3 + c // 3
if val in rows[r] or val in cols[c] or val in boxes[b]:
return False
rows[r].add(val)
cols[c].add(val)
boxes[b].add(val)
return TrueFrequently Asked Questions
What is the Valid Sudoku problem?
Determine if a 9x9 Sudoku board is valid according to the rules: each row, column, and 3x3 sub-box must contain digits 1-9 without repetition. The board may be partially filled; you only need to validate the existing entries, not whether it is solvable.
How do you solve Valid Sudoku?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Valid Sudoku?
Valid Sudoku is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Valid Sudoku?
- Clarify: only filled cells matter; dots are ignored.
- Hash sets can be replaced with bitmasks for O(1) extra space.
- Be careful with box indexing: (row/3)*3 + col/3 maps each cell to its 3x3 box.
- Interviewers may ask to also solve the board — that is a separate backtracking problem.
- Confirm whether the input is guaranteed to be a 9x9 board.