NUHMAN.com

Introduction

LeetCode 36: Valid Sudoku asks you to validate if a given 9x9 Sudoku board is valid according to the rules of Sudoku:

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 3x3 subgrids must also contain the digits 1-9 without repetition.

This problem tests your ability to check for duplicates in rows, columns, and subgrids efficiently.

Problem Statement

Given a 9x9 2D board, where each cell is a number or '.' (empty), determine if the Sudoku board is valid.

The board is valid if:

• Each row must contain no duplicate numbers.
• Each column must contain no duplicate numbers.
• Each of the nine 3x3 subgrids must contain no duplicate numbers.

Return true if the board is valid, otherwise return false.

Examples

go

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
go

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

Approach: Hashing (Set) Approach

To efficiently track duplicates, we'll use three hash sets:

• One for each row.
• One for each column.
• One for each 3x3 subgrid.

We'll iterate through the entire board:

1. For each number in the board, check if it's already in the respective row, column, or subgrid.
2. If any of these sets already contain the number, return false.
3. If no duplicates are found, return true.

Go Implementation

go

func isValidSudoku(board [][]byte) bool {
    rows := make([]map[byte]bool, 9)
    cols := make([]map[byte]bool, 9)
    boxes := make([]map[byte]bool, 9)
    
    for i := 0; i < 9; i++ {
        rows[i] = make(map[byte]bool)
        cols[i] = make(map[byte]bool)
        boxes[i] = make(map[byte]bool)
    }

    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                continue
            }
            num := board[i][j]
            boxIndex := (i/3)*3 + j/3
            
            if rows[i][num] || cols[j][num] || boxes[boxIndex][num] {
                return false
            }
            rows[i][num] = true
            cols[j][num] = true
            boxes[boxIndex][num] = true
        }
    }

    return true
}

Example Walkthrough

For the board:

go

[["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"]]

1. Row 0: Check for duplicates. No duplicates found.
2. Row 1: Check for duplicates. No duplicates found.
3. Repeat this process for each row, column, and subgrid.

After iterating through the board, the function returns true since there are no duplicates.

Time and Space Complexity

MetricComplexityTime ComplexityO(1)Space ComplexityO(1)

• The board is a fixed size (9x9), so the time complexity is effectively constant (O(1)), though it depends on the size of the input.
• We use three 9-sized hash sets, which also leads to constant space complexity.

Edge Cases

• Board has all empty cells ('.') → return true (since no validation needed).
• Board with invalid subgrids or rows/columns should correctly return false.

Key Takeaways

• Hashing is a powerful technique for problems like Sudoku where we need to check for duplicate elements in a row, column, or subgrid.
• This approach ensures efficient validation by using constant time operations with the help of hash maps.