54. Spiral Matrix - Leetcode Solution

LeetCode problem Solution code

đź’ˇ Step-by-Step Thought Process

  1. Understand the problem: Traverse an m x n matrix in a spiral order (right, down, left, up) and return all elements in a list.
  2. Get the dimensions of the matrix: m (rows) and n (columns).
  3. Initialize an empty list ans to store the spiral order elements.
  4. Initialize pointers i (row) and j (column) to 0, and a direction variable to RIGHT (1), with other directions UP (0), DOWN (2), and LEFT (3).
  5. Initialize boundaries: UP_WALL to 0, RIGHT_WALL to n, DOWN_WALL to m, and LEFT_WALL to -1.
  6. While the length of ans is less than m * n, process each direction:
  7. For RIGHT: While j is less than RIGHT_WALL, append matrix[i][j] to ans, increment j. Then, increment i, decrement j, reduce RIGHT_WALL by 1, set direction to DOWN.
  8. For DOWN: While i is less than DOWN_WALL, append matrix[i][j] to ans, increment i. Then, decrement i, decrement j, reduce DOWN_WALL by 1, set direction to LEFT.
  9. For LEFT: While j is greater than LEFT_WALL, append matrix[i][j] to ans, decrement j. Then, decrement i, increment j, increment LEFT_WALL by 1, set direction to UP.
  10. For UP: While i is greater than UP_WALL, append matrix[i][j] to ans, decrement i. Then, increment i, increment j, increment UP_WALL by 1, set direction to RIGHT.
  11. Return ans as the spiral order of the matrix.

Code Solution

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        ans = []
        i, j = 0, 0
        UP, RIGHT, DOWN, LEFT = 0, 1, 2, 3
        direction = RIGHT

        UP_WALL = 0
        RIGHT_WALL = n
        DOWN_WALL = m
        LEFT_WALL = -1

        while len(ans) != m*n:
            if direction == RIGHT:
                while j < RIGHT_WALL:
                    ans.append(matrix[i][j])
                    j += 1
                i, j = i+1, j-1
                RIGHT_WALL -= 1
                direction = DOWN
            elif direction == DOWN:
                while i < DOWN_WALL:
                    ans.append(matrix[i][j])
                    i += 1
                i, j = i-1, j-1
                DOWN_WALL -= 1
                direction = LEFT
            elif direction == LEFT:
                while j > LEFT_WALL:
                    ans.append(matrix[i][j])
                    j -= 1
                i, j = i-1, j+1
                LEFT_WALL += 1
                direction = UP
            else:
                while i > UP_WALL:
                    ans.append(matrix[i][j])
                    i -= 1
                i, j = i+1, j+1
                UP_WALL += 1
                direction = RIGHT
        
        return ans 
        # Time: O(m*n) 
        # Space: O(1)

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if (matrix.empty()) return ans;

        int m = matrix.size();
        int n = matrix[0].size();
        int UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;
        int direction = RIGHT;

        int UP_WALL = 0;
        int RIGHT_WALL = n;
        int DOWN_WALL = m;
        int LEFT_WALL = -1;

        int i = 0, j = 0;

        while (ans.size() != m * n) {
            if (direction == RIGHT) {
                while (j < RIGHT_WALL) {
                    ans.push_back(matrix[i][j]);
                    j++;
                }
                i++;
                j--;
                RIGHT_WALL--;
                direction = DOWN;
            } else if (direction == DOWN) {
                while (i < DOWN_WALL) {
                    ans.push_back(matrix[i][j]);
                    i++;
                }
                i--;
                j--;
                DOWN_WALL--;
                direction = LEFT;
            } else if (direction == LEFT) {
                while (j > LEFT_WALL) {
                    ans.push_back(matrix[i][j]);
                    j--;
                }
                i--;
                j++;
                LEFT_WALL++;
                direction = UP;
            } else {
                while (i > UP_WALL) {
                    ans.push_back(matrix[i][j]);
                    i--;
                }
                i++;
                j++;
                UP_WALL++;
                direction = RIGHT;
            }
        }

        return ans;
    }
};

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix.length == 0) return ans;

        int m = matrix.length;
        int n = matrix[0].length;
        int UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;
        int direction = RIGHT;

        int UP_WALL = 0;
        int RIGHT_WALL = n;
        int DOWN_WALL = m;
        int LEFT_WALL = -1;

        int i = 0, j = 0;

        while (ans.size() != m * n) {
            if (direction == RIGHT) {
                while (j < RIGHT_WALL) {
                    ans.add(matrix[i][j]);
                    j++;
                }
                i++;
                j--;
                RIGHT_WALL--;
                direction = DOWN;
            } else if (direction == DOWN) {
                while (i < DOWN_WALL) {
                    ans.add(matrix[i][j]);
                    i++;
                }
                i--;
                j--;
                DOWN_WALL--;
                direction = LEFT;
            } else if (direction == LEFT) {
                while (j > LEFT_WALL) {
                    ans.add(matrix[i][j]);
                    j--;
                }
                i--;
                j++;
                LEFT_WALL++;
                direction = UP;
            } else {
                while (i > UP_WALL) {
                    ans.add(matrix[i][j]);
                    i--;
                }
                i++;
                j++;
                UP_WALL++;
                direction = RIGHT;
            }
        }

        return ans;
    }
}

var spiralOrder = function(matrix) {
    let ans = [];
    if (matrix.length === 0) return ans;

    let m = matrix.length;
    let n = matrix[0].length;
    const UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;
    let direction = RIGHT;

    let UP_WALL = 0;
    let RIGHT_WALL = n;
    let DOWN_WALL = m;
    let LEFT_WALL = -1;

    let i = 0, j = 0;

    while (ans.length !== m * n) {
        if (direction === RIGHT) {
            while (j < RIGHT_WALL) {
                ans.push(matrix[i][j]);
                j++;
            }
            i++;
            j--;
            RIGHT_WALL--;
            direction = DOWN;
        } else if (direction === DOWN) {
            while (i < DOWN_WALL) {
                ans.push(matrix[i][j]);
                i++;
            }
            i--;
            j--;
            DOWN_WALL--;
            direction = LEFT;
        } else if (direction === LEFT) {
            while (j > LEFT_WALL) {
                ans.push(matrix[i][j]);
                j--;
            }
            i--;
            j++;
            LEFT_WALL++;
            direction = UP;
        } else {
            while (i > UP_WALL) {
                ans.push(matrix[i][j]);
                i--;
            }
            i++;
            j++;
            UP_WALL++;
            direction = RIGHT;
        }
    }

    return ans;
};

Detailed Explanation

Understanding the Problem: Spiral Matrix

The “Spiral Matrix” problem is a classic 2D array traversal question. Given an m x n matrix, your goal is to return all its elements in a spiral order—starting from the top-left corner and moving right, then down, then left, then up, and repeating this pattern inward until all elements are visited.

For example, if the input is:

123
456
789
The output should be: [1, 2, 3, 6, 9, 8, 7, 4, 5].

Why This Problem Matters

This problem strengthens your understanding of matrix boundaries, direction handling, and loop control logic. It simulates real-world data processing patterns such as image filtering, robotic movement in 2D grids, or navigation algorithms in game development.

Intuition Behind the Spiral Movement

The spiral pattern can be visualized as a set of layers or “walls” that shrink as you complete each full cycle (right → down → left → up). Each layer peels off one ring of the matrix. To manage this, we maintain four boundaries:

  • UP_WALL: the top boundary of unvisited rows
  • RIGHT_WALL: the right boundary of unvisited columns
  • DOWN_WALL: the bottom boundary of unvisited rows
  • LEFT_WALL: the left boundary of unvisited columns

As we traverse in a direction, we shrink the corresponding boundary to prevent re-visiting already-traversed cells.

Algorithm: Step-by-Step Approach

  1. Determine the number of rows (m) and columns (n) in the matrix.
  2. Initialize an empty list ans to store the spiral order result.
  3. Initialize direction variable with possible values: RIGHT, DOWN, LEFT, UP.
  4. Use pointers i (row) and j (column) to track the current position.
  5. Set up wall boundaries:
    • UP_WALL = 0
    • DOWN_WALL = m
    • LEFT_WALL = -1
    • RIGHT_WALL = n
  6. Loop until ans.length === m * n:
    • Right: Move while j < RIGHT_WALL. Append matrix[i][j] to result and increment j. After the loop, adjust pointers and decrement RIGHT_WALL.
    • Down: Move while i < DOWN_WALL. Append matrix[i][j] and increment i. Then decrement DOWN_WALL.
    • Left: Move while j > LEFT_WALL. Append matrix[i][j] and decrement j. Then increment LEFT_WALL.
    • Up: Move while i > UP_WALL. Append matrix[i][j] and decrement i. Then increment UP_WALL.

Example Walkthrough

Input:

123
456
789
Spiral steps:

  • Right → 1, 2, 3
  • Down → 6, 9
  • Left → 8, 7
  • Up → 4
  • Right → 5 (center element)

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

Time and Space Complexity

Time Complexity: O(m Ă— n), since we visit each element of the matrix exactly once.
Space Complexity: O(1) extra space (not counting the output array).

Edge Cases to Consider

  • Empty matrix → return []
  • 1x1 matrix → return the single element
  • 1-row or 1-column matrix → spiral is simply the original order
  • Non-square matrix → ensure the algorithm handles unequal dimensions

Conclusion

The “Spiral Matrix” problem helps build intuition for controlled matrix traversal and multi-directional logic. By maintaining clear boundaries and moving in controlled directions, you can elegantly extract a spiral order from a 2D array. Mastering this problem improves your confidence in handling grid-based tasks, which are foundational in both interviews and real-world systems like image processing, simulations, and game development.

NEW!Need help landing software roles? đź’ˇ