LeetCode Solution: 54. Spiral Matrix

#leetcode #dsa #programming #tutorial

Unraveling the Matrix: A Spiral Adventure! (LeetCode 54)

Hey there, fellow coders! 👋 Vansh here, ready to embark on another exciting LeetCode journey with you. Today, we're tackling a classic problem that might look intimidating at first glance, but I promise, it's a delightful puzzle once you get the hang of it: Problem 54: Spiral Matrix.

Imagine you have a grid of numbers, like a treasure map. Instead of going straight, you need to collect the treasures by moving in a continuous spiral path, starting from the top-left corner and moving inwards. Sounds fun, right? Let's dive in!

🗺️ Problem Explanation: The Spiral Challenge

The problem asks us to take a given m x n matrix (think of it as a 2D array or a grid) and return all its elements in a specific order: spiral order.

What does "spiral order" mean?
You start at the top-left, go right, then down, then left, then up, and keep repeating this pattern, but each time you move inward.

Let's look at the examples to make it crystal clear:

Example 1:

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

Think of it like this:

1 2 3
4 5 6
7 8 9

The spiral path would be:

Go Right: 1, 2, 3
Go Down: 6, 9 (from the last element of the right path)
Go Left: 8, 7 (from the last element of the down path)
Go Up: 4 (from the last element of the left path)
Go Right (inward): 5 (from the last element of the up path)

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

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

Visually:

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]

Notice how we stop going in a direction if we hit a boundary or an already visited element. The goal is to collect all elements exactly once.

🤔 Intuition: The Boundary Dance

My "aha!" moment for this problem came when I realized it's all about boundaries. Instead of thinking about complex pathfinding, imagine shrinking the matrix from its edges.

You start with an outer "layer" of the matrix, traverse its four sides, and once you're done with that layer, you effectively "peel" it off. Then, you're left with a smaller matrix in the middle, and you repeat the process until all elements are visited.

Think of it like this:

You have a startingRow and an endingRow.
You have a startingCol and an endingCol.

Initially, these define the outermost rectangle. You collect elements from this rectangle:

Top side (from startingCol to endingCol in startingRow).
Right side (from startingRow + 1 to endingRow in endingCol).
Bottom side (from endingCol - 1 to startingCol in endingRow).
Left side (from endingRow - 1 to startingRow + 1 in startingCol).

After each step, you shrink the boundaries inwards (increment startingRow, decrement endingCol, etc.) and repeat the cycle. You stop when your startingRow crosses endingRow or startingCol crosses endingCol, meaning you've covered the entire matrix.

🚀 Approach: Step-by-Step Logic

Let's break down the spiral traversal into actionable steps:

Initialize Variables:
- ans: A vector<int> (or ArrayList in Java) to store our spiral-ordered elements.
- row: Number of rows in the matrix.
- col: Number of columns in the matrix.
- count: To keep track of how many elements we've visited so far.
- total: The total number of elements in the matrix (row * col). We'll stop when count == total.
- Boundary Pointers:
  - startingRow = 0
  - startingCol = 0
  - endingRow = row - 1
  - endingCol = col - 1
Main Loop: We'll use a while (count < total) loop to continue as long as there are elements left to visit.
Traverse Each Side (and update boundaries):

*   **a. Traverse Right (First Row):**
    *   Iterate from `index = startingCol` to `endingCol`.
    *   Add `matrix[startingRow][index]` to `ans`.
    *   Increment `count`.
    *   **Important:** After this step, we've processed the `startingRow`, so move the `startingRow` pointer down: `startingRow++`.

*   **b. Traverse Down (Last Column):**
    *   **Crucial Check:** Before starting any traversal, always check `if (count < total)`! This handles cases where the matrix is fully traversed in an earlier step (e.g., a single row matrix).
    *   Iterate from `index = startingRow` to `endingRow`.
    *   Add `matrix[index][endingCol]` to `ans`.
    *   Increment `count`.
    *   **Important:** We've processed the `endingCol`, so move the `endingCol` pointer left: `endingCol--`.

*   **c. Traverse Left (Last Row):**
    *   **Crucial Check:** `if (count < total)`!
    *   Iterate from `index = endingCol` down to `startingCol`.
    *   Add `matrix[endingRow][index]` to `ans`.
    *   Increment `count`.
    *   **Important:** We've processed the `endingRow`, so move the `endingRow` pointer up: `endingRow--`.

*   **d. Traverse Up (First Column):**
    *   **Crucial Check:** `if (count < total)`!
    *   Iterate from `index = endingRow` down to `startingRow`.
    *   Add `matrix[index][startingCol]` to `ans`.
    *   Increment `count`.
    *   **Important:** We've processed the `startingCol`, so move the `startingCol` pointer right: `startingCol++`.

Return ans: Once the while loop finishes (when count == total), all elements have been collected.

The count < total checks within each for loop are vital. They prevent out-of-bounds errors or duplicate additions when dealing with non-square matrices or matrices with a single row/column, where the boundaries might overlap or cross prematurely.

💻 Code: Bringing the Spiral to Life!

Here's the C++ implementation based on our approach:

#include <vector> // Required for std::vector

class Solution {
public:
    std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
        std::vector<int> ans;

        int row = matrix.size();
        if (row == 0) return ans; // Handle empty matrix
        int col = matrix[0].size();

        int count = 0;
        int total = row * col;

        // Index initialization for boundaries
        int startingRow = 0;
        int startingCol = 0;
        int endingRow = row - 1;
        int endingCol = col - 1;

        while (count < total) {

            // 1. Print starting row (left to right)
            for (int index = startingCol; count < total && index <= endingCol; index++) {
                ans.push_back(matrix[startingRow][index]);
                count++;
            }
            startingRow++; // Move starting row boundary down

            // 2. Print ending column (top to bottom)
            for (int index = startingRow; count < total && index <= endingRow; index++) {
                ans.push_back(matrix[index][endingCol]);
                count++;
            }
            endingCol--; // Move ending column boundary left

            // 3. Print ending row (right to left)
            for (int index = endingCol; count < total && index >= startingCol; index--) {
                ans.push_back(matrix[endingRow][index]);
                count++;
            }
            endingRow--; // Move ending row boundary up

            // 4. Print starting column (bottom to top)
            for (int index = endingRow; count < total && index >= startingRow; index--) {
                ans.push_back(matrix[index][startingCol]);
                count++;
            }
            startingCol++; // Move starting column boundary right
        }
        return ans;
    }
};

⏱️ Complexity Analysis

Time Complexity: O(m * n)
- We visit each element in the m x n matrix exactly once to add it to our result array. Therefore, the time taken scales linearly with the total number of elements.
Space Complexity: O(m * n)
- We create a new vector (or ArrayList) ans to store all m * n elements of the matrix. This space is directly proportional to the size of the input matrix. If we consider auxiliary space not counting the output, it would be O(1). However, since the problem requires returning the elements in a new data structure, O(m*n) is the standard answer.

✅ Key Takeaways

Boundary Manipulation: This problem is a prime example of using boundary pointers (startingRow, endingRow, startingCol, endingCol) to define and shrink the active processing area.
Iterative Approach: Breaking down a complex traversal into four simple, repetitive steps (right, down, left, up) is key.
Crucial Edge Case Checks: The count < total condition within each for loop is absolutely essential! It prevents incorrect behavior and out-of-bounds access when the matrix becomes too small or has a non-standard shape (e.g., a single row or column). Without it, you might try to traverse a row/column that no longer exists in the "shrunken" matrix.
Visualizing is Key: Drawing out the matrix and tracing the path for a few steps can greatly help in understanding how the boundaries should be updated.

This spiral traversal pattern is common in interviews, so understanding this approach will definitely boost your problem-solving toolkit! Keep practicing, keep coding, and I'll see you in the next LeetCode adventure!

Author Account: Vansh2710
Time Published: 2026-03-30 23:27:53