Table of Contents
Open Table of Contents
Problem
Given a 9x9 Sudoku board, determine if it is valid. A Sudoku board is valid if:
 Each row contains the digits 19 without repetition.
 Each column contains the digits 19 without repetition.
 Each of the nine 3x3 subboxes contains the digits 19 without repetition.
Note:
 A partially filled Sudoku board could be valid but not necessarily solvable.
 Only filled cells need to be validated.
Example 1:
Input:
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Example 2:
Input:
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Constraints:
board.length == 9
board[i].length == 9
board[i][j]
is a digit 19 or ’.‘.
Explanation/Approach
Using Hash Sets:
 Row, Column, and Box Validation: Create separate hash sets for each row, column, and 3x3 subbox.
 Iterating Over the Board: Traverse the board and check each cell. If a cell is not empty (’.’), validate its value against the corresponding row, column, and subbox hash sets.
 Hash Set Update: If the value is not present in the relevant sets, add it. If it’s already present, the Sudoku is invalid.
 Box Index Calculation: To calculate the index of the subbox, use
(row // 3) * 3 + col // 3
.
Solution: Using Hash Sets
from collections import defaultdict
class Solution:
def isValidSudoku(self, board: List[List[str]]) > bool:
rows = defaultdict(set)
columns = defaultdict(set)
boxes = defaultdict(set)
for i in range(9):
for j in range(9):
num = board[i][j]
if num != '.':
box_index = (i // 3) * 3 + j // 3
if num in rows[i] or num in columns[j] or num in boxes[box_index]:
return False
rows[i].add(num)
columns[j].add(num)
boxes[box_index].add(num)
return True
Time and Memory Complexity
 Time Complexity: O(1), as the board size is fixed at 9x9, leading to a constant number of operations.
 Memory Complexity: O(1), as the extra space used (hash sets) is constant and independent of the input size.
Visual Representation
For Example 1:

Check each cell and update the corresponding row, column, and box sets.

If a number repeats in any row, column, or 3x3 subbox, return
False
. 
Example: On encountering ‘5’ in row 1, column 1, check if ‘5’ exists in the corresponding sets. If not, add it.

Continue this for all cells.

If no violations are found, return
True
.