Problem:
Given a matrix , collect the elements in the matrix in a spiral direction clockwise and return them as a list.
For example:
Consider the matrix [[1,2,3],[4,5,6],[7,8,9]]
You need to traverse the matrix spirally like below:
So the output is :
[1,2,3,6,9,8,7,4,5]
Try out the solution here:
https://leetcode.com/problems/spiral-matrix/
Solution:
Hint:
Traverse right , then down , then left and finally up.
Do this until all the elements are traversed.
Approach 1: Traverse using pointers to the start row , start column and total number of rows and columns
In this approach we will use four major pointers.
Start Row
Start Column
Number of Rows
Number of Columns
Once you finish traversing one square in the spiral these values will change
For example,
After one round ,
Start Row will become 1
Start Column will become 1
No of Rows will be less by two (first row and last row will be ignored)
No of Columns will be less by two (first column and last column will be ignored)
You can continue traversing the squares until the number of columns or the number of rows becomes 0.
We need to consider two base conditions separately.
What if the square contains only one row or only one column.
Then you add all the elements in the row or column and return the list.
Here is the detailed algorithm:
STEP 1: Initialize four pointers , two for start of row and column , two for number of rows and columns.
STEP 2: While both number of rows and columns are non zero do the following:
STEP 2a: Check if there is only one row or column then return all the elements in a list
STEP 2b: Collect elements by traversing right leaving out the last element (last element will be picked in next step)
STEP 2c: Collect elements by traversing down leaving out the last element (last element will be picked in next step)
STEP 2d: Collect elements by traversing left leaving out the last element (last element will be picked in next step)
STEP 2e: Collect elements by traversing up
STEP 2f: Increment both start row and start column pointers and decrement number of rows and number of columns by two.
STEP 3: Return output.
Code:
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> output = new ArrayList<Integer>();
int startRow = 0;
int startCol = 0;
int noOfRows = matrix.length;
int noOfCols = matrix[0].length;
while(noOfCols > 0 && noOfRows > 0){
int c = 0;
int r = 0;
if(noOfRows ==1 ){
for(int i=0;i<noOfCols;i++){
output.add(matrix[startRow][startCol+i]);
}
break;
}
if(noOfCols ==1 ){
for(int i=0;i<noOfRows;i++){
output.add(matrix[startRow+i][startCol]);
}
break;
}
while(c < noOfCols-1){
output.add(matrix[r+startRow][c+startCol]);
c++;
}
while(r < noOfRows-1){
output.add(matrix[r+startRow][c+startCol]);
r++;
}
while(c > 0){
output.add(matrix[r+startRow][c+startCol]);
c--;
}
while(r > 0){
output.add(matrix[r+startRow][c+startCol]);
r--;
}
noOfRows -= 2;
noOfCols -= 2;
startCol++;
startRow++;
}
return output;
}
}
The time complexity is O(m*n) where m is the number of rows and n the number of columns respectively.
Space complexity is also O(m*n) since we use a list whose size is in proportion to the input matrix.
This solution is fast as evident below in leetcode.com:
Approach2: Using pointers to start and end of rows and columns
The first approach was created by the author of this post .
The second approach discussed below got the most upvotes in leetcode discussions.
It uses four pointers : two to the start of rows and columns and two to the end of rows and columns.
These get adjusted as you traverse the matrix in a spiral way.
You traverse right and collect elements and then increment the start Row pointer
You traverse down and collect elements and then decrement the end Column pointer
You traverse left and collect elements and then decrement the end row pointer
You traverse up and collect elements and then increment the start column pointer
This way the outer square gets traversed and you are left with the start and end pointers to the inner square now.
Here is the algorithm:
ALGORITHM:
STEP 1: Initialize four pointers to the start and end of the rows and columns
STEP 2: While start row pointer is less than or equal to the end row pointer and start column pointer is less than or equal to the end column pointer do the following:
STEP 2a: Starting from the start column pointer to the end column pointer collect all elements and then increment the start row pointer
STEP 2b: Starting from the start row pointer to the end row pointer collect all elements and then decrement the end column pointer
STEP 2c: Starting from the end column pointer to the start column pointer collect all elements and decrement the row end pointer. Check if row start pointer is less than or equal to row end pointer before collecting the elements. The check should not be done for decrementing row end pointer.
STEP 2d: Starting from the row end pointer to the row start pointer collect all elements and increment the column pointer. Check if column start pointer is less than or equal to column end pointer before collecting the elements. The check should not be done for incrementing the column pointer.
STEP 3: Return the output.
Here is the code:
Code:
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> output = new ArrayList<Integer>();
if(matrix.length ==0) return output;
int rowBegin = 0;
int colBegin = 0;
int rowEnd = matrix.length-1;
int colEnd = matrix[0].length-1;
while(rowBegin<= rowEnd && colBegin <=colEnd){
//traverse right
for(int i=colBegin;i<=colEnd;i++){
output.add(matrix[rowBegin][i]);
}
rowBegin++;
//traverse down
for(int i=rowBegin;i<=rowEnd;i++){
output.add(matrix[i][colEnd]);
}
colEnd--;
//traverse left
if(rowBegin<=rowEnd){
for(int i=colEnd;i>=colBegin;i--){
output.add(matrix[rowEnd][i]);
}
}
rowEnd--;
//traverse up
if(colBegin <= colEnd){
for(int i=rowEnd;i>=rowBegin;i--){
output.add(matrix[i][colBegin]);
}
}
colBegin++;
}
return output;
}
}
Time complexity is O(m * n ) where m is the number of rows and n the number of columns
Space complexity is also O(m * n ) since we collect all the elements in the matrix to a separate list of the same size.
That’s it!
Leave a Reply