36.Valid_Sudoku_(Medium).md

36. Valid Sudoku (Medium)

Update: Jun 5, 2024, 3:38 PM (EST)

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

Question:

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.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.

• Only the filled cells need to be validated according to the mentioned rules.

KeyPoints:

Use three dicts to save each entry into colSet{}, rowSet{}, boxSet{}, loop over matrix to add entry's value into three sets, check if there is repetition exists, if so, return False. If we have '.', we continue.

Python Solution:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Use three dicts to save each col, row, sub-box with val
        # Get sub-box by (r//3, c//3)
        # If val is '.', we skip
        # If val is repeated, return False

        # TC: O(n^2), n=rows, SC: O(n^2)
        colSet, rowSet, boxSet = collections.defaultdict(set), collections.defaultdict(set), collections.defaultdict(set)
        rows, cols = len(board), len(board[0])

        # Loop over matrix to add elements into sets
        for r in range(rows):
            for c in range(cols):
                val = board[r][c]
                # Skip '.'
                if val == '.':
                    continue
                # Check if repetition, return False
                if val in rowSet[r] or val in colSet[c] or val in boxSet[(r//3, c//3)]:
                    return False
                # Add entry into 3 sets
                rowSet[r].add(val)
                colSet[c].add(val)
                boxSet[(r//3, c//3)].add(val)
        return True

Time Complexity: $O(n^2)$, the area of the Sudoku.
Space Complexity: $O(n^2)$