Medium·[2025-12-22]
36. Valid Sudoku
[#matrix]
## description
## 36. Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- 1.Each row must contain the digits 1-9 without repetition.
- 2.Each column must contain the digits 1-9 without repetition.
- 3.Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without 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:
plain text
1Input: board =
2[["5","3",".",".","7",".",".",".","."]
3,["6",".",".","1","9","5",".",".","."]
4,[".","9","8",".",".",".",".","6","."]
5,["8",".",".",".","6",".",".",".","3"]
6,["4",".",".","8",".","3",".",".","1"]
7,["7",".",".",".","2",".",".",".","6"]
8,[".","6",".",".",".",".","2","8","."]
9,[".",".",".","4","1","9",".",".","5"]
10,[".",".",".",".","8",".",".","7","9"]]
11Output: trueExample 2:
plain text
1Input: board =
2[["8","3",".",".","7",".",".",".","."]
3,["6",".",".","1","9","5",".",".","."]
4,[".","9","8",".",".",".",".","6","."]
5,["8",".",".",".","6",".",".",".","3"]
6,["4",".",".","8",".","3",".",".","1"]
7,["7",".",".",".","2",".",".",".","6"]
8,[".","6",".",".",".",".","2","8","."]
9,[".",".",".","4","1","9",".",".","5"]
10,[".",".",".",".","8",".",".","7","9"]]
11Output: false
12Explanation: 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.- –board.length == 9
- –board[i].length == 9
- –board[i][j] is a digit 1-9 or '.'.
Constraints:
## notes
### Intuition
A valid Sudoku has no duplicates in any row, column, or 3×3 subbox. We need to verify all three constraints independently.
### Implementation
Use hashmaps to track seen values. First, iterate through each row checking for duplicates. Then iterate through each column. Finally, check each of the nine 3×3 subboxes. Skip empty cells (".") during all checks.
### Edge-cases
The 3×3 subbox indexing is tricky. Use four nested loops: box_row (0-2), box_col (0-2), row (0-2), col (0-2). Access cells with board[3 * box_row + row][3 * box_col + col].
- –Time: O(1) — board is always 9×9, so effectively constant
- –Space: O(1) — hashmaps hold at most 9 elements each
### Complexity
## solution
python
1from typing import List
2
3class Solution:
4 def isValidSudoku(self, board: List[List[str]]) -> bool:
5
6 # Check rows
7 for row in range(len(board)):
8 map = {}
9 for col in range(len(board[row])):
10 if board[row][col] == ".":
11 continue
12 if board[row][col] in map:
13 return False
14 map[board[row][col]] = True
15
16 # Check cols
17 for col in range(len(board)):
18 map = {}
19 for row in range(len(board[col])):
20 if board[row][col] == ".":
21 continue
22 if board[row][col] in map:
23 return False
24 map[board[row][col]] = True
25
26 # Check sub boxes
27 for brow in range(3):
28 for bcol in range(3):
29 map = {}
30 for row in range(3):
31 for col in range(3):
32 if board[3 * brow + row][3 * bcol + col] == ".":
33 continue
34 if board[3 * brow + row][3 * bcol + col] in map:
35 return False
36 map[board[3 * brow + row][3 * bcol + col]] = True
37 return True
38
39
40
41
42if __name__ == "__main__":
43 # Include one-off tests here or debugging logic that can be run by running this file
44 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
45 solution = Solution()
46--EOF--