NUHMAN.com

Introduction

LeetCode 59: Spiral Matrix II is a classic problem where you're asked to generate a n x n matrix filled with numbers from 1 to n² in spiral order. This problem challenges your understanding of matrix traversal and boundary control.

It’s a great way to practice array manipulation and looping over 2D data structures.

Problem Statement

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n² in spiral order.

Example 1:

go

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

Example 2:

go

Input: n = 1
Output: [
 [1]
]

Constraints

• 1 <= n <= 20

Approach: Layer-by-Layer Spiral Filling

The approach is similar to the spiral matrix traversal problem (LeetCode 54). We'll create a matrix of size n x n and fill it in a spiral order by iterating layer by layer.

Steps:

1. Initialize boundaries: top, bottom, left, and right pointers.
2. Start with the number 1, and fill in the matrix by moving in the right, down, left, and up directions.
3. After filling in a direction, adjust the corresponding boundary and proceed to the next direction.

Go Implementation

go

func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }

    top, bottom, left, right := 0, n-1, 0, n-1
    num := 1

    for top <= bottom && left <= right {
        // Traverse from left to right
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++

        // Traverse from top to bottom
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--

        // Traverse from right to left
        if top <= bottom {
            for i := right; i >= left; i-- {
                matrix[bottom][i] = num
                num++
            }
            bottom--
        }

        // Traverse from bottom to top
        if left <= right {
            for i := bottom; i >= top; i-- {
                matrix[i][left] = num
                num++
            }
            left++
        }
    }

    return matrix
}

Example Walkthrough

For input n = 3, initialize the matrix and set the boundaries:

• Start: top = 0, bottom = 2, left = 0, right = 2

1. Fill the first row from left to right: 1, 2, 3

• Update top = 1

1. Fill the last column from top to bottom: 4, 5

• Update right = 1

1. Fill the last row from right to left: 6, 7

• Update bottom = 1

1. Fill the first column from bottom to top: 8

• Update left = 1

1. Final number is 9.

Resulting matrix:

go

[
  [1, 2, 3],
  [8, 9, 4],
  [7, 6, 5]
]

Time and Space Complexity

MetricComplexityTime ComplexityO(n²)Space ComplexityO(n²)

The matrix requires O(n²) space, and each element is processed exactly once, resulting in O(n²) time complexity.

Edge Cases

• n = 1: Simple case where the matrix is just [1].
• n = 2: The matrix will be filled as:

go

[[1, 2], 
 [4, 3]]

Key Takeaways

• The spiral filling technique is elegant and easy to implement with boundary tracking.
• Great for practicing traversal of 2D arrays and controlling boundaries.
• Efficient solution with a time complexity of O(n²) for filling the matrix.