Valid Sudoku

Medium Subject: Arrays & Hashing

Time Complexity

O(1)

Space Complexity

O(1)

Problem Description

Problem Statement

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.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."]],["6",".",".","1","9","5",".",".","."]],[".","9","8",".",".",".",".","6","."]],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: true

Optimal Solution

Python

Approach: Hash Sets for Rows, Columns, and Boxes

We can use hash sets to keep track of the numbers we have seen in each row, each column, and each 3x3 sub-box. If we encounter a number that is already in the corresponding row, column, or box set, the board is invalid.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set) # key = (r // 3, c // 3)

        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

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