LeetCode Solution 54 - Spiral Matrix

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input:

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

Output:

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

Example 2:

Input:

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

Output:

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

---

Optimal Approach

The optimal way to solve this problem is using boundaries and direction changes. We maintain four boundaries: top, bottom, left, and right. We iterate through the matrix in a spiral order, adjusting the boundaries after traversing each row or column.

Algorithm:

1. Initialize top = 0, bottom = m - 1, left = 0, right = n - 1.
2. Traverse from left to right and increment top.
3. Traverse from top to bottom and decrement right.
4. Traverse from right to left (if within bounds) and decrement bottom.
5. Traverse from bottom to top (if within bounds) and increment left.
6. Repeat until all elements are visited.

---

C++ Code (LeetCode Compatible)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        if (matrix.empty()) return result;
        
        int m = matrix.size(), n = matrix[0].size();
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; ++i) result.push_back(matrix[top][i]);
            ++top;
            
            for (int i = top; i <= bottom; ++i) result.push_back(matrix[i][right]);
            --right;
            
            if (top <= bottom) {
                for (int i = right; i >= left; --i) result.push_back(matrix[bottom][i]);
                --bottom;
            }
            
            if (left <= right) {
                for (int i = bottom; i >= top; --i) result.push_back(matrix[i][left]);
                ++left;
            }
        }
        
        return result;
    }
};

---

Step-by-Step Explanation

1. Initialization: Set top, bottom, left, and right boundaries.
2. Left to Right: Traverse the top row and increment top.
3. Top to Bottom: Traverse the rightmost column and decrement right.
4. Right to Left: Traverse the bottom row if it's in bounds and decrement bottom.
5. Bottom to Top: Traverse the leftmost column if it's in bounds and increment left.
6. Repeat: Continue this process until all elements are visited.

---

Dry Run

Input:

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

Execution Steps:

1. Left to Right: [1,2,3] (top moves down)
2. Top to Bottom: [6,9] (right moves left)
3. Right to Left: [8,7] (bottom moves up)
4. Bottom to Top: [4] (left moves right)
5. Left to Right: [5]

Output:

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

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Nested Loops)	O(m*n)	O(m*n)	Requires extra memory to track visited elements.
DFS Recursive Approach	O(m*n)	O(m*n)	Extra recursive calls lead to a larger stack size.

---

Best Solution & Why It’s Best

The boundary-based traversal method is the most efficient because:

• Time Complexity: O(m*n), since we visit each element once.
• Space Complexity: O(1), as no extra space is used except the result array.
• Directly modifies boundaries without extra data structures.

---

Complexity Analysis

• Time Complexity: O(m*n), as every element is processed once.
• Space Complexity: O(1), aside from the output vector.

---

Conclusion

• The boundary-based traversal is the best approach.
• It efficiently handles matrix traversal without extra space.
• Related Problems:
  • Spiral Matrix II
  • Rotate Image
  • Diagonal Traverse

This solution is LeetCode-compatible and optimized for real-world coding interviews. 🚀