LeetCode 36. Valid Sudoku

November 4, 2024

Now, I am working on matrix problems.

Solution

This is my initial greedy solution.

1class Solution:
2    def isValidSudoku(self, board: List[List[str]]) -> bool:
3        for row in board:
4            rowVals = set()
5            for column in row:
6                if column != '.' and column in rowVals:
7                    return False
8                rowVals.add(column)
9
10        for col in range(len(board[0])):
11            colVals = set()
12            for row in board:
13                if row[col] != '.' and row[col] in colVals:
14                    return False
15                colVals.add(row[col])
16
17        for subX in range(3):
18            for subY in range(3):
19                gridVals = set()
20                for x in range(3):
21                    for y in range(3):
22                        cell = board[subY * 3 + y][subX * 3 + x]
23                        if cell != '.' and cell in gridVals:
24                            return False
25                        gridVals.add(board[subY * 3 + y][subX * 3 + x])
26        
27        return True

Improvements

Now, I reviewed other solutions and liked this one which uses a list of tuples and only one nested for loop.

1class Solution:
2    def isValidSudoku(self, board: List[List[str]]) -> bool:
3        vals = []
4        for i, row in enumerate(board):
5            for j, x in enumerate(row):
6                if x != '.':
7                    vals += [(x, j), (i, x), (x, i // 3, j // 3)]
8        return len(vals) == len(set(vals))

I like how tuples are made unique by swapping their position, and the cell value is not mistaken for the row/column because it is a string rather than int. O(n) = 1 since board size is fixed.

LeetCode 76. Minimum Window Substring

LeetCode 48. Rotate Image