Solving the LeetCode "Spiral Matrix" Problem in Go

Difficulty: Medium | Tags: Array, Matrix, Simulation

Introduction

The "Spiral Matrix" problem requires traversing a 2D matrix in a spiral order, starting from the top-left corner and moving clockwise. This problem tests your ability to manipulate matrix indices and handle boundary conditions.

Problem Analysis

Given an m x n matrix, the task is to return all elements in spiral order. For example, the matrix [[1,2,3],[4,5,6],[7,8,9]] should return [1,2,3,6,9,8,7,4,5]. The challenge lies in navigating the matrix layers while avoiding revisiting elements.

Solution Approach

The solution involves traversing the matrix layer by layer, starting from the outermost layer and moving inward. We define four boundaries: top, bottom, left, and right. We traverse right, down, left, and up, adjusting the boundaries after each traversal until all elements are covered.

Go Implementation

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }
    result := []int{}
    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1
    for top <= bottom && left <= right {
        // Traverse from left to right on top row
        for i := left; i <= right; i++ {
            result = append(result, matrix[top][i])
        }
        top++
        // Traverse from top to bottom on right column
        for i := top; i <= bottom; i++ {
            result = append(result, matrix[i][right])
        }
        right--
        if top <= bottom {
            // Traverse from right to left on bottom row
            for i := right; i >= left; i-- {
                result = append(result, matrix[bottom][i])
            }
            bottom--
        }
        if left <= right {
            // Traverse from bottom to top on left column
            for i := bottom; i >= top; i-- {
                result = append(result, matrix[i][left])
            }
            left++
        }
    }
    return result
}

Complexity Analysis

The time complexity is O(m * n), where m is the number of rows and n is the number of columns, as we visit each element exactly once. The space complexity is O(1) for the variables used, but O(m * n) for the output array, which is required by the problem.

Testing and Examples

Test the function with the following cases:

• Example 1: [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]
• Example 2: [[1,2,3,4],[5,6,7,8],[9,10,11,12]] → [1,2,3,4,8,12,11,10,9,5,6,7]
• Edge Case: Empty matrix [][] → []
• Single Row: [[1,2,3]] → [1,2,3]
• Single Column: [[1],[2],[3]] → [1,2,3]

Best Practices and Tips

Key takeaways include:

• Clearly define and update boundaries to avoid index errors.
• Handle edge cases like single-row or single-column matrices separately if needed.
• Use descriptive variable names for clarity.
• Test with small and large matrices to ensure robustness.