Video Solution (Short)
Problem Overview
Difficulty: Medium
LeetCode Pattern: Hashing
Determine if a 9 x 9 Sudoku board is valid according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 boxes of the grid must contain the digits 1-9 without repetition.
Note:
Only the filled cells need to be validated according to the mentioned rules.
For unfilled cells in the matrix, assume it would be the dot (.) character.
Example 1
Valid Case.
It satisfies all properties.
Example 2
Invalid Case.
Two 8's in the top left 3x3 box.
Step 1: Clarify Requirements
Can the board have all empty cells?
Yes, that’s possible.
Can there by values other than 1-9?
No, assume values are 1-9 only.
Can board size be other than 9x9?
No, assume 9x9 board only.
Step 2: Discuss Approaches
Approach 1: Brute Force
Logic:
For each filled cell:
Check every value in that row
Check every value in that col
Check every value in that box
If no match → return True
If match found → return False
Big O:
Time Complexity: O(n3)
Space Complexity: O(1)
Approach 2: Use Multiple Sets (Optimal)
Logic:
Create 27 sets in total:
9 for rows
9 for cols
9 for boxes
For each filled cell:
Check value in:
row set
col set
box set
If value exists → return False
Else → add to sets and continue
At the end:
return True (valid board)
Big O:
Time Complexity: O(n2)
Space Complexity: O(1)
Step 3: Write Code
Python
Java
C++
Step 4: Answer Follow-Ups
What if the board was nearly empty?
Our algorithm still works fine.
It will simply skip most cells.
What if board contains invalid chars?
We can add validation checks.
If an invalid char is found:
Return False (invalid board), or
Throw an error (bad input).
What if the board size was any nxn?
Replace hardcoded 9 with n.
Box Size is now: sqrt(n) × sqrt(n).
Rest of algorithm stays the same.
Big O remains the same as well.
👨💻 Need Interview Practice?
Book a 1:1 with me
Book Here: Booking URL