Problem Statement
We are given a partially filled 9x9 Sudoku board. We need to validate whether the current state of the board is valid or not. A board is considered valid if:
- Each row contains digits 1–9 without repetition.
- Each column contains digits 1–9 without repetition.
- Each of the nine 3x3 sub-boxes contains digits 1–9 without repetition.
Empty cells may be represented by
0 or '.' Approach
- Create 9 sets for each row, column, and 3x3 box
- For every filled cell
mat[i][j]: - Skip if the value is
0. - Calculate the box index using:
boxIndex = 3 * (i / 3) + (j / 3) - Check if the value already exists in:
row[i]col[j]box[boxIndex]- If any set already contains the value, return
false. - Otherwise, insert the value into all three sets.
Time and Space Complexity
- Time Complexity:
O(81)=O(1)
(Since the board is always 9x9)
- Space Complexity:
O(27)=O(1)
(9 sets each for row, column, and box)
