Valid Sudoku
- 1 min read
- LC-Medium
3 years ago
Solution
- Use three hashmaps to check in if a number is not supposed to exist in a row, column, or sub-square
- The indexing of the subsquare set is going to be a tuple of (r // 3, c // 3)
- If you want to use a list instead of a dictionary, the index is (r // 3) * 3 + (c // 3)
| Time | Space | Explanation |
|---|---|---|
O(mn) | O(m) or O(n) |
def isValidSudoku(self, board: List[List[str]]) -> bool:
# Initialize defaultdicts for rows, columns, and sub-boxes
row_set = defaultdict(set)
col_set = defaultdict(set)
sub_set = defaultdict(set)
# Go through each number, add each number to set. If number is already seen in a set, return False
for r in range(len(board)):
for c in range(len(board[0])):
num = board[r][c]
if num != '.':
if num in row_set[r] or num in col_set[c] or num in sub_set[(r // 3, c // 3)]:
return False
row_set[r].add(num)
col_set[c].add(num)
sub_set[(r // 3, c // 3)].add(num)
# If code reaches here, sudoku board is valid, so return True
return True