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] <= 100The Spiral Matrix problem asks you to return all elements of a 2D matrix in spiral order. The key idea is to simulate the traversal layer by layer while maintaining four boundaries: top, bottom, left, and right. These boundaries represent the current outer layer of the matrix that has not yet been visited.
At each step, traverse in four directions: move left-to-right across the top row, top-to-bottom along the right column, right-to-left across the bottom row, and bottom-to-top along the left column. After completing each direction, update the corresponding boundary to shrink the traversal region. Continue this process until the boundaries cross.
This approach works well because it avoids revisiting elements and cleanly models the spiral pattern using simple index updates. The traversal touches each element exactly once, making it efficient for large matrices. Care must be taken to check boundary conditions after each step to prevent duplicate traversals in cases where the matrix has uneven dimensions.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Boundary Simulation (Spiral Traversal) | O(m × n) | O(1) extra space (excluding output) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.
We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column, and then we move inwards by 1 and repeat. That's all. That is all the simulation that we need.
Think about when you want to switch the progress on one of the indexes. If you progress on i out of [i, j], you'll shift in the same column. Similarly, by changing values for j, you'd be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It's always best to simulate edge cases like a single column or a single row to see if anything breaks or not.
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, intThe 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.
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.
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.
1def spiralOrder(matrix):
2 result = []
3 ifWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Spiral Matrix is a common medium-level interview problem asked in companies like Amazon, Google, and Microsoft. It tests matrix traversal skills, boundary handling, and simulation logic.
The optimal approach is boundary-based simulation. Maintain four pointers representing the current top, bottom, left, and right boundaries and traverse the matrix in four directions while shrinking the boundaries after each pass.
A frequent mistake is not checking boundary conditions after updating pointers, which can cause duplicate traversal of rows or columns. Handling matrices with a single row or column also requires careful checks.
The problem mainly uses arrays since the input is a 2D matrix. No additional complex data structures are required—just index variables to track boundaries and a list to store the traversal order.
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.