Valid Sudoku - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Valid Sudoku" Problem in Go

Difficulty: Medium | Tags: Array, Hash Table, Matrix

Introduction

Validating a Sudoku board is a classic problem that tests your ability to work with matrices and hash tables efficiently. The challenge is to ensure that the given 9x9 board adheres to the rules of Sudoku without necessarily being solvable.

Problem Analysis

The problem requires checking three conditions: no duplicates in rows, columns, or 3x3 sub-boxes. Only filled cells (digits 1-9) need validation, while empty cells ('.') are ignored. The examples illustrate valid and invalid boards based on these rules.

Solution Approach

We use hash sets to track seen digits in rows, columns, and sub-boxes. For each cell, we check if the digit has already been seen in its respective row, column, or sub-box. If a duplicate is found, the board is invalid.

Go Implementation


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++ {
            val := board[i][j]
            if val == '.' {
                continue
            }
            // Check row
            if rows[i][val] {
                return false
            }
            rows[i][val] = true
            // Check column
            if cols[j][val] {
                return false
            }
            cols[j][val] = true
            // Check sub-box
            boxIdx := (i/3)*3 + j/3
            if boxes[boxIdx][val] {
                return false
            }
            boxes[boxIdx][val] = true
        }
    }
    return true
}

Complexity Analysis

Time Complexity: O(1) or O(9x9) = O(81), since the board size is fixed. We traverse each cell exactly once.

Space Complexity: O(1) or O(3x9x9) = O(243), as we use three hash sets for rows, columns, and sub-boxes, each storing up to 9 entries per row/column/box.

Testing and Examples

Test the solution with the provided examples:

Example 1:
Input: Valid board
Output: true
Example 2:
Input: Invalid board (duplicate in sub-box)
Output: false

Additional edge cases include empty boards, fully filled valid boards, and boards with duplicates in rows or columns.

Best Practices and Tips

1. Use separate hash sets for rows, columns, and sub-boxes to simplify checks.

2. Calculate the sub-box index using integer division: boxIdx = (i/3)*3 + j/3.

3. Ignore empty cells ('.') to optimize performance.

4. Prefer maps over arrays for cleaner code, though arrays could also work with fixed sizes.

Read more