36. Valid Sudoku
Asked at Apple
Difficulty
Medium
Time
O(1)
Space
O(1)
Pattern
Array
Companies
1
Problem
You are given a 9 x 9 Sudoku board. Each cell holds a digit from '1' to '9', or '.' if the cell is empty. Decide whether the board is valid.
A board is valid when no digit repeats inside any row, inside any column, or inside any of the nine 3 x 3 sub-boxes. Empty cells are ignored — you only check the cells that already hold a digit.
Important: a valid board does not have to be solvable. You are not asked to fill in the empty cells. You only report whether the digits that are already there break any of the three rules. Return true if nothing is broken, otherwise false.
Three rules to check
Constraints
- ●
board.length == 9 - ●
board[i].length == 9 - ●
board[i][j] is a digit 1-9 or '.'
Examples
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],[trueboard = [["8","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],[falseAsked At
1 companies| 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.
One pass with 27 sets
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
O(1) timeclass 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 runs in O(1) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.