Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] 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]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100Problem Overview: Given an m x n matrix, return all elements of the matrix in spiral order. Start at the top-left corner, traverse the top row, then the right column, the bottom row in reverse, and the left column upward. Continue shrinking the boundaries until every element is visited exactly once.
Approach 1: Iterative Boundary Management (Time: O(m*n), Space: O(1))
This approach simulates the spiral traversal by maintaining four boundaries: top, bottom, left, and right. You iterate across the top row from left to right, then move the top boundary down. Next iterate down the right column and move the right boundary left. Continue with the bottom row (right to left) and the left column (bottom to top), shrinking the boundaries after each pass. The key insight is that each layer of the matrix forms a rectangle that can be processed in four directional passes. Since every element is visited exactly once, the time complexity is O(m*n), and only a few integer pointers are used, giving O(1) extra space.
This is primarily a simulation problem on a matrix. The algorithm directly models the traversal path rather than transforming the data. Boundary checks after each traversal prevent duplicate visits when the matrix collapses to a single row or column.
Approach 2: Recursive Divide and Conquer (Time: O(m*n), Space: O(min(m,n)))
The recursive approach processes the matrix layer by layer. Each recursive call reads the outer perimeter: traverse the top row, right column, bottom row in reverse, and left column upward. After completing the perimeter, recursively call the same logic on the inner submatrix defined by top+1, bottom-1, left+1, and right-1. Each recursion removes one rectangular layer until the boundaries cross.
The time complexity remains O(m*n) because every element is still visited once. The difference is the recursion stack, which can grow up to the number of spiral layers, roughly min(m,n)/2. That results in O(min(m,n)) auxiliary space due to recursion. This version is shorter and expressive in languages like Python, but iterative logic is usually preferred in production code.
Both approaches rely on careful index control within an array-backed grid. Edge cases occur when the remaining region collapses into a single row or column, so boundary checks must run after every directional traversal.
Recommended for interviews: Iterative boundary management is the expected solution. Interviewers want to see that you can simulate matrix traversal using pointer boundaries without extra memory. The recursive version demonstrates clean thinking about layers, but the iterative approach shows stronger control over indices and edge cases.
This approach involves simulating the spiral order by iteratively traversing matrix layers. The boundaries are adjusted after each complete traversal of a side (top, right, bottom, left). By shrinking the boundaries, we can eventually cover the entire matrix in a spiral order.
The C solution uses a while loop to traverse the matrix. It defines boundaries for the layers (top, bottom, left, right) and adjusts these boundaries after completing the traversal of each side. The movement is controlled by the boundary variables, ensuring the entire matrix is spirally covered.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns, since each element is accessed once.
Space Complexity: O(1) additional space, excluding the space for the output array.
This approach uses recursion to divide the matrix into smaller sections. By processing the outer layer of the matrix, we can recursively call the function on the remaining submatrix. This continues until the entire matrix is covered.
The Python solution defines a recursive helper function `spiral_layer`, with parameters defining the boundaries of the current submatrix. The base condition checks if the boundary indices are valid. It extracts and appends elements to the result, then recursively narrows the boundaries until they converge.
Time Complexity: O(m * n) since each recursive call processes an entire layer of the matrix.
Space Complexity: O(m * n) due to the recursive call stack usage, although tail recursion may optimize this depending on the Python implementation.
| Approach | Complexity |
|---|---|
| Iterative Boundary Management | Time Complexity: O(m * n) where m is the number of rows and n is the number of columns, since each element is accessed once. Space Complexity: O(1) additional space, excluding the space for the output array. |
| Recursive Divide and Conquer | Time Complexity: O(m * n) since each recursive call processes an entire layer of the matrix. Space Complexity: O(m * n) due to the recursive call stack usage, although tail recursion may optimize this depending on the Python implementation. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Boundary Management | O(m*n) | O(1) | Best general solution for interviews and production. Uses constant memory and straightforward boundary pointers. |
| Recursive Divide and Conquer | O(m*n) | O(min(m,n)) | Useful when expressing the problem in layers recursively. Cleaner in Python but adds recursion stack overhead. |
Spiral Traversal of a Matrix | Spiral Matrix • take U forward • 308,263 views views
Watch 9 more video solutions →Practice Spiral Matrix with our built-in code editor and test cases.
Practice on FleetCode