Solving the LeetCode "Spiral Matrix II" Problem in Go

Difficulty: Medium | Tags: Array, Matrix, Simulation

Introduction

The "Spiral Matrix II" problem requires generating an n x n matrix filled with numbers from 1 to n² in a spiral order. This problem tests your ability to simulate traversal patterns and manage matrix indices effectively.

Problem Analysis

Given a positive integer n, the task is to create an n x n matrix where elements are filled in a spiral order, starting from the top-left corner and moving clockwise. For example, when n = 3, the output should be [[1,2,3],[8,9,4],[7,6,5]]. The challenge lies in correctly navigating the matrix boundaries while filling the values.

Solution Approach

The solution involves simulating the spiral traversal by maintaining four boundaries: top, bottom, left, and right. We fill the matrix layer by layer, adjusting the boundaries after completing each layer. The steps are as follows:

1. Initialize the matrix and set boundaries.
2. Fill the top row from left to right, then increment the top boundary.
3. Fill the right column from top to bottom, then decrement the right boundary.
4. Fill the bottom row from right to left (if top ≤ bottom), then decrement the bottom boundary.
5. Fill the left column from bottom to top (if left ≤ right), then increment the left boundary.
6. Repeat until all elements are filled.

Go Implementation

func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    top, bottom := 0, n-1
    left, right := 0, n-1
    num := 1
    for top <= bottom && left <= right {
        // Fill top row from left to right
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++
        // Fill right column from top to bottom
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--
        // Fill bottom row from right to left (if applicable)
        if top <= bottom {
            for i := right; i >= left; i-- {
                matrix[bottom][i] = num
                num++
            }
            bottom--
        }
        // Fill left column from bottom to top (if applicable)
        if left <= right {
            for i := bottom; i >= top; i-- {
                matrix[i][left] = num
                num++
            }
            left++
        }
    }
    return matrix
}

Complexity Analysis

Time Complexity: O(n²) since we fill all n² elements in the matrix exactly once.

Space Complexity: O(n²) for storing the resulting matrix. The auxiliary space used is O(1) as we only use a few variables for boundaries and tracking the current number.

Testing and Examples

Example 1: n = 3 → Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2: n = 1 → Output: [[1]]

Edge Case: n = 2 → Output: [[1,2],[4,3]]

Best Practices and Tips

1. Clearly define boundaries and update them correctly after each traversal.

2. Handle edge cases like n = 1 separately if it simplifies the logic.

3. Use descriptive variable names (e.g., top, bottom) to improve code readability.

4. Test with small and large values of n to ensure correctness.