Problem Statement
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.length
- n == matrix[ i ].length
- 1 <= m, n <= 10
- -100 <= matrix[ i ][ j ] <= 100
Disclaimer: These kinds of problems look difficult but can be broken down by creating a simulation or a simple algorithm. Before proceeding forward toward the solution it is recommended to try first!!
Intuition
If we closely look at the problem, we will be able to easily figure out that the spiral traversal can be easily done by using four variables: top, down, left, and right. There will be the following four directions:
- Direction 1: left -> right
- Direction 2: top -> bottom
- Direction 3: right -> left
- Direction 4: bottom -> top
The above directions can be easily simulated by using four different loops for each direction. Once we have traversed in one direction we only need to modify the variables slightly in order to move forward in another direction.
It is important ‼️ to note that the terminating condition for stopping the traversal will be met as soon as top > bottom or left > right.
Approach
- In order to store our spiral traversal we will first create a 1D array. Also, we need to traverse in four directions for which we will create variables as follows:
- ans: 1D array
- top = 0
- bottom = matrix.size – 1 (number of rows in the matrix)
- left = 0
- right = matrix[0].size -1 (number of columns in the matrix)
- Now, we will start a loop and keep on traversing the matrix in the spiral order until either top > bottom or left > right. Within the loop, we will be having the four steps.
- STEP 1: Traverse the matrix from left to right and keep on appending the elements into the ID array created before. Once we have traversed the matrix we will increase the top by 1. This would mean that we have traversed the top from left to right.
- STEP 2: Next, in a similar manner, we will traverse the matrix from top to bottom. Once we have traversed the matrix we will decrease right by 1. This means that we have traversed the right end from top to bottom.
- STEP 3: Next, we will traverse the matrix from right to left. Once we have traversed the matrix we will decrease the bottom by 1. This means that we have traversed the bottom of the matrix from right to left.
- STEP 4: Our last step would be to traverse the matrix from bottom to top. Once we have traversed the matrix we will increase the left by 1. This would mean that we have traversed the left end of the matrix from bottom to top.
- As we still need to traverse the remaining part of the martix, therefore we will loop again and traverse the remaining part of the matrix in a similar manner.
- After we have completely traversed the matrix we will get the spiral order in the 1D array that we created in the beginning.
Code
'''
* Author: behl1anmol
* T(n): O(m+n), linear time complexity because we are traversing the elements of the matrix only once.
* S(n): O(1).
'''
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int>ans;
if(matrix.size()==0) return ans;
int top = 0;
int bottom = matrix.size()-1;
int left = 0;
int right = matrix[0].size()-1;
while(top<=bottom && left<=right){
for(int i = left; i<=right; i++) ans.push_back(matrix[top][i]);
top++;
for(int i = top; i<=bottom; i++) ans.push_back(matrix[i][right]);
right--;
for(int i=right; i>=left && top<=bottom ;i--) ans.push_back(matrix[bottom][i]);
bottom--;
for(int i=bottom; i>=top && left<=right; i--) ans.push_back(matrix[i][left]);
left++;
}
return ans;
}
};
Time Complexity
- T(n): O(m+n), linear time complexity because we are traversing the elements of the matrix only once.
- S(n): O(1), assuming that the extra space for storing and returning the spiral array is neglected.
Awesome 👏