[Top Interview 150] 36. Valid Sudoku

Solution)

 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Dictionaries that have values of sets
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

        # Iterating 9 rows
        for r in range(9):
            # Iterating 9 columns
            for c in range(9):
                # If the current number doesn't exist
                if board[r][c] == ".":
                    continue

                # If the current number was seen in one of
                # its row, column, or square return False
                if (board[r][c] in rows[r] or
                    board[r][c] in cols[c] or
                    board[r][c] in squares[(r // 3, c // 3)]):
                    return False

                # If not seen, add the current number in dictionaries
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])
        
        return True

 
 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n^2)
Space Complexity: O(n^2)

 

 

Explanation)

To check if the board is valid we have 3 conditions.
 
1) A row cannot have a duplicate number
2) A column cannot have a duplicate number
3) A square cannot have a duplicate number
* Board doesn't have to be solvable
 
First, we add the numbers in board to a certain space.
We'll use three dictionaries cols, rows, and squares to save those numbers.
Below are the depictions of the three dictionaries
 
 

rows Dictionary)

rows will save numbers in nine rows of the board.
Indices of the nine rows will be the key, and the numbers in each row will be the values. Those numbers will be saved in sets.
 
 

rows dictionary of {index of a row : set of numbers in a row}

 
 

cols Dictionary)

cols will save numbers in nine columns of the board.
Indices of the nine columns will be the key, and the set of numbers in each column will be the values.
 
 

cols dictionary of {index of a column : set of numbers in a column}

 

squares Dictionary)

squares will save numbers in nine 3X3 subsquares of the board.
Tuple indeces of the nine subsqures will be the key, and the set of numbers in each suqsquare will be the values.
 
 

squares dictionary of {tuple index of a subsquare : set of numbers in a subsquare}

For mapping the keys of subsquares, we use an integer division.
 
For example, say we want to check a number in (0, 0) subsquare.
How do we know if the current number is in that subsquare?
 
If the current number is located in 1st row and 0th column. We know that the number is in (0, 0) subsquare.
The mapping can be done by doing (1 // 3, 0 // 3). By integer dividing the current row and column by three, we're able to get a tuple that indicates which subsquare the current number belongs to.
 
If the current number is located in 2nd row and 7th column. According to our mapping, the tuple would be (2 // 3, 7 // 3) which is (0, 2). So we know that the number belongs to (0, 2) subsquare.
 
 

Initialization)

Let's make three dictionaries that will take sets as their values.
 

def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

 

 

If the current number doesn't exist)

We would need to use nested for loops of range of 9. 
We do this so that we can check all 81 numbers in board.
 
So to check the number in 0th row and 0th column, we would check board[0][0].
 
And as we check all 81 numbers, there may be a case where there isn't a number but an empty space.
In that case, we wouldn't want to add that blank space to our dictionary so we skip the loop using the keyword continue.
 

def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue

 
 

If the current number is a duplicate)

How would we know if the current number is a duplicate?
 
We can find this by checking if the current number exists in one of the current row, column, or subsquare.
Then how do we check this?
 
To check if the current number was seen in the current row for example, we would check if the number is in rows[current row]. rows[current row] is a set of all numbers that were seen in the current row.
 
We repeat this process for cols and squares dictionaries as well.
If the duplicate was found in one of the three sets, we return False. 
 

def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Initialization

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue

                if (board[r][c] in rows[r] or
                    board[r][c] in cols[c] or
                    board[r][c] in squares[(r // 3, c // 3)]):
                    return False

If the current number is a new number)

If all the conditions above weren't the case, that means the current number is a new number!
 
Then, we need to add the new number to the three dictionaries so that we can use this information to check if this new number has a duplicate for future numbers.
 
Add the new number to the sets of current rows, cols, and squares.
 
 
If False wasn't returned, the board is a valid board thus we return True.
 

def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

        for r in range(9):
            for c in range(9):
                # If the number doesn't exist

                if (board[r][c] in rows[r] or
                    board[r][c] in cols[c] or
                    board[r][c] in squares[(r // 3, c // 3)]):
                    return False

                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])
        
        return True

 
 
 
The problem wasn't so bad but even if I knew how to sovle matrix problems, finding the mapping logic for subsquares would have been tough. Hopefully I don't watch NeetCode for the next problem.