LeetCode 36 - Valid Sudoku

Table of Contents

Problem

Given a 9x9 Sudoku board, determine if it is valid. A Sudoku board is valid if:

• Each row contains the digits 1-9 without repetition.
• Each column contains the digits 1-9 without repetition.
• Each of the nine 3x3 sub-boxes contains the digits 1-9 without repetition.

Note:

• A partially filled Sudoku board could be valid but not necessarily solvable.
• Only filled cells need to be validated.

Example 1:

Input:
[["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

Example 2:

Input:
[["8","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: false

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or ’.‘.

Explanation/Approach

Using Hash Sets:

• Row, Column, and Box Validation: Create separate hash sets for each row, column, and 3x3 sub-box.
• Iterating Over the Board: Traverse the board and check each cell. If a cell is not empty (’.’), validate its value against the corresponding row, column, and sub-box hash sets.
• Hash Set Update: If the value is not present in the relevant sets, add it. If it’s already present, the Sudoku is invalid.
• Box Index Calculation: To calculate the index of the sub-box, use (row // 3) * 3 + col // 3.

Solution: Using Hash Sets

from collections import defaultdict

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)
        columns = defaultdict(set)
        boxes = defaultdict(set)

        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    box_index = (i // 3) * 3 + j // 3
                    if num in rows[i] or num in columns[j] or num in boxes[box_index]:
                        return False
                    rows[i].add(num)
                    columns[j].add(num)
                    boxes[box_index].add(num)
        return True

Time and Memory Complexity

• Time Complexity: O(1), as the board size is fixed at 9x9, leading to a constant number of operations.
• Memory Complexity: O(1), as the extra space used (hash sets) is constant and independent of the input size.

Visual Representation

For Example 1:

• Check each cell and update the corresponding row, column, and box sets.

• If a number repeats in any row, column, or 3x3 sub-box, return False.

• Example: On encountering ‘5’ in row 1, column 1, check if ‘5’ exists in the corresponding sets. If not, add it.

• Continue this for all cells.

• If no violations are found, return True.