Spiral Matrix
Problem Description
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Example 2:
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
Solve it on LeetCode
Approaches
1. Simulation
Intuition:
The problem is about collecting numbers in a matrix in a defined "spiral order". We can simulate this process by keeping track of boundaries that govern the visible "layer" of the matrix being iterated upon. Initially, these boundaries correspond to the full extent of the matrix, and they contract as we pick up elements in spiral fashion.
We maintain four boundaries:
- Top boundary: starts at the first row and moves downward.
- Bottom boundary: starts at the last row and moves upward.
- Left boundary: starts at the first column and moves rightward.
- Right boundary: starts at the last column and moves leftward.
By traversing these boundaries in the correct sequence, we can extract the elements of the matrix in spiral order.
Steps:
- Traverse the top row from left boundary to right boundary, then move the top boundary downward.
- Traverse the right column from top boundary to bottom boundary, then move the right boundary leftward.
- Traverse the bottom row from right boundary to left boundary, then move the bottom boundary upward.
- Traverse the left column from bottom boundary to top boundary, then move the left boundary rightward.
- Repeat until all boundaries meet or cross each other.
Code:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Every element in the matrix is visited exactly once.
- Space Complexity: O(1), excluding the space used by the output list.
2. Optimized
Intuition:
A more structured version of the basic approach relies on cycling through four directions: right, down, left, and up. We can simplify by using a direction index to manage changes in direction and move uniformly until a boundary condition stops us.
Steps:
- Define coordinates changes for directions:
(0,1)for right,(1,0)for down,(0,-1)for left,(-1,0)for up. - Use an index to rotate through these directions as necessary.
- For each movement action, validate if the destination is within unvisited cells.
- Adjust direction and mark cell as visited when hitting a boundary.
Code:
- Time Complexity: O(m * n), since each cell of the matrix is visited exactly once.
- Space Complexity: O(m * n), due to the visited matrix tracking visited cells.