Valid Sudoku

Problem

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.

2. Each column must contain the digits 1-9 without repetition.

3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Solution

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = set()
        column = set()
        block = set()
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] != ".":   
                    r = (i,board[i][j])
                    c = (j, board[i][j])
                    b = (i//3,j//3, board[i][j])
                
                    if r in row or c in column or b in block:
                        return False
                
                    row.add(r)
                    column.add(c)
                    block.add(b)
        
        return True
        
#We need to keep track of the digits we see in each row,
#column, and block

#We will have 3 hash sets (row, column, block), storing the
#number along with the row/column/block we saw the 
#number in. Whenever we encounter a digit already seen,
#we know the sudoku is not valid.

#Time: O(n^2)
#Space: O(n) for the sets