Valid Sodoku

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• You are given a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:
  1. Each row must contain the digits 1-9 without duplicates.
  2. Each column must contain the digits 1-9 without duplicates.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.
• Return true if the Sudoku board is valid, otherwise return false
• Note: A board does not need to be full or be solvable to be valid.

Solution

• I initially thought that a good solution would be to do two loops, one for the rows, and one for the columns.
• Then, keep an hashmap of sets of digits in each row, column, and 3x3 subgrid
  • I think a good way to keep track of the subgrids index is to use floor division by 3

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
	    # time complexity: O(n^2)
	    # space complexity: O(n^2)
    
        cols = defaultdict(set)
        rows = defaultdict(set)
        subgrids = defaultdict(set)
 
        for r in range(9):
            for c in range(9):
                item = board[r][c]
 
                if item == '.':
                    continue
 
                if (item in rows[r]
	                or item in cols[c]
					or item in subgrids[(r // 3, c // 3)]
				):
                    return False
 
                cols[c].add(item)
                rows[r].add(item)
                subgrids[(r // 3, c // 3)].add(item)
 
        return True
 

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───