In this tutorial we will learn how to Spiral A Matrix with examples. In other words Spirally Traverse of a Matrix using best approach of algorithm. This is a part of Data Structure.
How To Spiral A Matrix?
We have a input Matrix as shown above. It could have any length. Now we have to traversal it Spirally as show below.
Traversing the input Matrix Spirally gives us the below output which is a Spiral Matrix.
Example:
Print a given Matrix in Spiral form by dividing into cycles
The problem can be solve by dividing the Matrix into loops or squire or boundaries. It can be seen that the elements of the outer loops are printed first in a clockwise manner then the elements of the inner loop are printed. So printing the elements of a loop can be solved using four loops that prints all the elements. Every for loop defines the single direction movement along with the Matrix. The first for loop represents the movement from left to right, whereas the second loop represents the movement from top to bottom, the third represents right to left and the last one represents from bottom to up movement.
Algorithm
Below is the example in Java. The algorithm remains same in all programming languages only the way of declaring the variables can be different.
We are using single while and for loop is used to solve this problem. Time complexity is O(MxN) and there is no extra space is required so the Auxiliary space taken is O(1)
Time Complexity: O(MxN)
Auxiliary Space: O(1)
import java.util.*;
class SpiralMatrix {
public static List<Integer> spiralOrder(int[][] matrix) {
int row = matrix.length;
List<Integer> ans = new ArrayList<>();
if(row<1){
return ans;
}
int col = matrix[0].length;
int startR = 0;
int startCol = 0;
int i =0;
while(startR<row&& startCol<col){
for(i= startCol; i< col; ++i){
ans.add(matrix[startR][i]);
}
startR++;
for(i = startR; i<row;++i){
ans.add(matrix[i][col-1]);
}
col--;
if(startR<row){
for(i = col-1; i>=startCol;--i){
ans.add(matrix[row-1][i]);
}
row--;
}
if(startCol<col){
for(i = row-1; i>=startR;--i){
ans.add(matrix[i][startCol]);
}
startCol++;
}
}
return ans;
}
public static void main(String args[]){
int[][] mat= {{ 1, 2, 3, 4 }, { 12, 13, 14, 5 }, { 11, 16, 15, 6 }, { 10, 9, 8, 7 } };
List<Integer> result = spiralOrder(mat);
System.out.print(result);
}
}Solving By JavaScript Algorithm
In the below example, same algorithm is used to solve this problem.
Thank you for visiting the tutorial, for any issue and doubts you can comment in the comment section below.
You can also see the examples on LeeteCode. for more examples by different different algorithms. Can You solve the Trapping Rain Water Problem.