LeetCode 36. Valid Sudoku - Solution Beats 92.52%

Problem    : https://leetcode.com/problems/valid-sudoku/

Solution    : https://leetcode.com/problems/valid-sudoku/solutions/3572587/92ms-beats-92-52-python-36-valid-sudoku-28-may-2023/

Submisson    : https://leetcode.com/problems/valid-sudoku/submissions/

Github code    :    https://github.com/ravivanjarapu/ProblemSolving/blob/main/LeetCode/36.%20Valid%20Sudoku.py

Intuition

Compare the list with set. If lengths are same, they are unique.

Approach

1. Exclude '.' and check if every row list length is same when compared with its set
2. Transpose the matrix and repeat above for all columns check
3. Take each 3x3 sub-matrix and convert to list. Compare the list with its set

Complexity

• Time complexity: O(3 n^2) --> O(n^2)

• Space complexity: O(9) --> O(1). Please correct me if I am wrong.

Proof:
Submission link: https://leetcode.com/problems/valid-sudoku/submissions/837321916/

Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        if not board:
            return False
        for row in board:
            temp = [i for i in row if i != '.']
            if len(set(temp)) != len(temp):
                return False

        transpose_dict = defaultdict(list)
        for row in board:
            for i in range(len(row)):
                if row[i] != '.':
                    transpose_dict[i].append(row[i])
        for k, v in transpose_dict.items():
            if len(v) != len(set(v)):
                return False

        for i in range(0, len(board), 3):
            for j in range(0, len(board), 3):
                box = []
                for k in range(i, i + 3):
                    box.extend(board[k][j:j + 3])

                box = [element for element in box if element != '.']
                if len(box) != len(set(box)):
                    return False
        return True

If you enjoyed this post, make sure you subscribe to my RSS feed! Comments are encouraged