You are given a matrix of integers, you need to print the matrix in spiral form.
For Example
: Consider a 2d array containing n rows and m number of columns, you need to print the matrix in spiral form without using any other matrix.
Input
Output
: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 The above output in spiral form.
Approach 1
If we analyze this problem very carefully, we see that there are four moments of the matrix in the first step. In the first step, the matrix is printed from left to right then right to bottom then bottom to the left, and then bottom-left to top. So to solve this problem, we create four pointers at each corner of the original matrix.
- The top pointer will point to the first column and first row of the given matrix.
- The right pointer will point to the first row and last column of the given matrix.
- The bottom pointer will point to the last column and last row of the given matrix.
- The left pointer will point to the last row and first column of the given matrix.
Implementation:
- Print the matrix from left to right order using the current position of the top as a row, then increase the top pointer.
- Print the matrix from right to bottom using the current position of the right pointer as a column, then decrease the right pointer value.
- Print the matrix from right to left using the current position of the bottom pointer as a row, then decrease the value of the bottom pointer.
- Print the matrix from bottom to top using the current position of the left pointer as a column, then increase the left pointer.
- Perform this iteration of printing of the matrix elements until the left pointer is smaller than equal to the write pointer and the top pointer is smaller than equal to the bottom pointer of the matrix.
JAVA:
//Importing libraries
import java.io.*;
import java.util.*;
//Creating Main class
class Main{
//Function to spiral matrix
static void print(ArrayListSpiralForm) {
for(int i=0;i<SpiralForm.size();++i) {
System.out.print(SpiralForm.get(i)+" ");
}
}
static void spiralMatrix(int matrix[][]) {
//Creating four pointers point the all corners of the matrix
int top=0;//top corner
int left=0;//left corner
//right corner
int right=matrix[0].length-1;
//bottom corner
int bottom=matrix.length-1;
//Checking the condition
while(left<=right&& top<=bottom) {
//Printing the rows
for(int i=left;i<=right;++i) {
System.out.print(matrix[top][i]+" ");
}
//Update the top pointer
++top;
for(int i=top;i<=bottom;++i) {
//Printing the column from top to bottom
System.out.print(matrix[i][right]+" ");
}
//Update the right pointer
--right;
//Checking the condition
if(top<=bottom) {
//Printing the row from right to left
for(int i=right;i>=left;--i) {
System.out.print(matrix[bottom][i]+" ");
}
//Update the bottom pointer
--bottom;
}
if(left<=right) {
//Printing the column from bottom to top
for(int i=bottom;i>=top;--i) {
System.out.print(matrix[i][left]+" ");
}
++left;
}
}
}
public static void main(String args[]) {
//Matrix
int matrix[][]= {{1,2,3},
{4,2,4}};
//Printing the spiral matrix
System.out.println("Printing the spiral matrix");
//Calling the function
spiralMatrix(matrix);
System.out.println();
}
}
Output:
C++:
//Importing libraries
#include <bits/stdc++.h>
using namespace std;
#define r 3
#define c 3
void spiralMatrix(int matrix[r][c]) {
//Creating four pointers point the all corners of the matrix
int top=0;//top corner
int left=0;//left corner
//right corner
int right=r-1;
//bottom corner
int bottom=c-1;
for(int i=0;i<r;++i){
for(int j=0;j<c;++j){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
//Checking the condition
while(left<=right && top<=bottom) {
//Printing the rows
for(int i=left;i<=right;++i) {
cout<<matrix[top][i]<<" ";
}
//Update the top pointer
++top;
for(int i=top;i<=bottom;++i) {
//Printing the column from top to bottom
cout<<matrix[i][right]<<" ";
}
//Update the right pointer
--right;
//Checking the condition
if(top<=bottom) {
//Printing the row from right to left
for(int i=right;i>=left;--i) {
cout<<matrix[bottom][i]<<" ";
}
//Update the bottom pointer
--bottom;
}
if(left<=right) {
//Printing the column from bottom to top
for(int i=bottom;i>=top;--i) {
cout<<matrix[i][left]<<" ";
}
++left;
}
}
int main() {
// Given Matrix
int matrix[r][c]= {{1,2,3},
{4,2,5},
{6,7,8}};
//Printing the spiral matrix
cout<<"Printing the spiral matrix"<<endl;
//Calling the spiralMatrix function
spiralMatrix(matrix);
cout<<endl;
return 0;
}
Output:
Python:
#Function to print the spiral matrix
def printspiral(mat):
#Creating Four reference that point to the all corners of the matrix
top=0
left=0
bottom=len(mat)-1
right=len(mat[0])-1
#Checking the condition
while left<=right and top<=bottom:
#Print the row first from left to right
for index in range(left,right+1):
print(mat[top][index],end=" ")
top=top+1
#Printing the matrix from top to bottom
for index in range(top,bottom+1):
print(mat[index][right],end=" ")
right=right-1
if(top<=right):
#Printing the matrix from right to left
for index in range(right,left-1,-1):
print(mat[bottom][index],end=" ")
bottom=bottom-1
#Printing the matrix from bottom to top
if(top<=bottom):
for index in range(bottom,top-1,-1):
print(mat[index][left],end=" ")
left=left+1
#Main Function
def main():
#Matrix
mat = [
[1,2,3]
,[4,5,6],
[7,8,9]
]
#Call Function to print the spiral matrix
print("Printing the matrix in the spiral form")
printspiral(mat)
print()
#Calling the main function
main()
Output:
Complexity :
- Time Complexity : The Time complexity of this approach is O(n^m). Where n is the total number of rows and m is the total number of columns in the original matrix.
- Space Complexity : The Space Complexity of this approach is O(1). Because in this approach all operations are done on an original matrix, that’s why the space complexity of this approach is O(1).
Approach 2 (Using Recursion approach):
In this approach, we will use recursion to solve this concept similar to the above approach . So to solve this problem we create four pointers at each corner of the original matrix.
- The top pointer will point to the first column and first row of the given matrix.
- The left-right pointer will point to the last column of the given matrix.
- The bottom pointer will point to the last column and last row of the given matrix.
- The left pointer will point to the last row and first column of the given matrix.
Implementation:
- Print the matrix from left to right order using the current position of the top as a row, then increase the top pointer.
- Print the matrix from right to bottom using the current position of the right pointer as a column, then decrease the right pointer value.
- Print the matrix from right to left using the current position of the bottom pointer as a row, then decrease the value of the bottom pointer.
- Print the matrix from bottom to top using the current position of the left pointer as a column, then increase the left pointer.
- Recursively call the function for the next top, bottom, left, right pointers of the matrix.
JAVA :
//Importing libraries
import java.util.*;
import java.io.*;
class Main{
//Function to print the spiral matrix
static void spiralmatrix(int matrix[][],int left_pointer,int right_pointer,int top_pointer,int bottom_pointer ){
//Printing the top row
//Checking the condition
if(left_pointer>right_pointer){
return;
}
//Printing the matrix from left to right
for(int i=left_pointer;i<=right_pointer;++i){
System.out.print(matrix[top_pointer][i]+" "); }
++top_pointer;
//Checking the condition
if(top_pointer>bottom_pointer){
return;
}
//Printing the matrix from top to bottom
for(int i=top_pointer;i<=bottom_pointer;++i){
System.out.print(matrix[i][right_pointer]+" ");
}
--right_pointer;
//Checking the condition
if(left_pointer>right_pointer)
return;
for(int i=right_pointer;i>=left_pointer;--i){
System.out.print(matrix[bottom_pointer][i]+" ");
}
--bottom_pointer;
//Checking the condition
if(top_pointer>bottom_pointer)
return;
//Printing the matrix from bottom to the top
for(int i=bottom_pointer;i>=top_pointer;--i){
System.out.print(matrix[i][left_pointer]+" ");
}
++left_pointer;
spiralmatrix(matrix, left_pointer, right_pointer, top_pointer, bottom_pointer);
}
public static void main(String[] args) {
int matrix[][]={{1,2,3},
{4,5,6},
{7,8,9}};
//Creating four pointers
int left=0;
int top=0;
int right=matrix[0].length-1;
int bottom=matrix.length-1;
//Call function to print the matrix int spiral form
System.out.println("Printing the matrix in the spiral form");
spiralmatrix(matrix,left,right,top,bottom);
System.out.println();
}
}
Output:
C++:
//Importing libraries
#include <bits/stdc++.h>
using namespace std;
#define r 3
#define c 3
void spiralMatrix(int matrix[r][c],int left_pointer,int right_pointer,int top_pointer,int bottom_pointer) {
//Printing the top row
//Checking the condition
if(left_pointer>right_pointer){
return;
}
//Printing the matrix from left to right
for(int i=left_pointer;i<=right_pointer;++i){
cout<<matrix[top_pointer][i]<<" ";
}
++top_pointer;
//Checking the condition
if(top_pointer>bottom_pointer){
return;
}
//Printing the matrix from top to bottom
for(int i=top_pointer;i<=bottom_pointer;++i){
cout<<matrix[i][right_pointer]<<" "; }
--right_pointer;
//Checking the condition
if(left_pointer>right_pointer)
return;
for(int i=right_pointer;i>=left_pointer;--i){
cout<<matrix[bottom_pointer][i]<<" "; }
--bottom_pointer;
//Checking the condition
if(top_pointer>bottom_pointer)
return;
//Printing the matrix from bottom to the top
for(int i=bottom_pointer;i>=top_pointer;--i){
cout<<matrix[i][left_pointer]<<" ";
}
++left_pointer;
spiralMatrix(matrix, left_pointer, right_pointer, top_pointer, bottom_pointer);
}
int main() {
// Given Matrix
int matrix[r][c]= {{1,2,3},
{4,2,5},
{6,7,8}};
//Creating Four pointers
int left=0;
int top=0;
int right=c-1;
int bottom=r-1;
//Printing the spiral matrix
cout<<"Printing the spiral matrix"<<endl;
spiralMatrix(matrix,left,right,top,bottom);
cout<<endl;
return 0;
}
Output:
Python:
#Function to print the spiral matrix
def printspiral(mat,left_pointer,right_pointer,top_pointer,bottom_pointer):
#Creating Four reference that point to the all corners of the matrix
#Checking the condition
if left_pointer>right_pointer:
return
#Print the row first from left to right
for index in range(left_pointer,right_pointer+1):
print(mat[top_pointer][index],end=" ")
top_pointer=top_pointer+1
#Checking the condition
if top_pointer>bottom_pointer:
return
#Printing the matrix from top to bottom
for index in range(top_pointer,bottom_pointer+1):
print(mat[index][right_pointer],end=" ")
right_pointer=right_pointer-1
#Checking the condition
if(left_pointer>right_pointer):
return
#Printing the matrix from right to left
for index in range(right_pointer,left_pointer-1,-1):
print(mat[bottom_pointer][index],end=" ")
bottom_pointer=bottom_pointer-1
#Checking the condition
if(top_pointer>bottom_pointer):
return
#Printing the matrix from bottom to top pointer
for index in range(bottom_pointer,top_pointer-1,-1):
print(mat[index][left_pointer],end=" ")
left_pointer=left_pointer+1
#Recursively call
return printspiral(mat,left_pointer,right_pointer,top_pointer,bottom_pointer)
#Main Function
def main():
#Matrix
mat = [
[1,2,3]
,[4,5,6],
[7,8,9]
]
#Call Function to print the spiral matrix
print("Printing the matrix in the spiral form")
#Creating Four pointers
top=0
left=0
bottom=len(mat)-1
right=len(mat[0])-1
printspiral(mat,left,right,top,bottom)
#Calling the main function
main()
Output:
Complexity :
- Time Complexity : The Time complexity of this approach is O(n^m). Where n is the total number of rows of the original matrix and m is the total number of columns of the matrix.
- Space Complexity : The Space Complexity of this approach is O(n^m). Where n is the total number of rows of the matrix and m is the total number of columns of the matrix. The Space Complexity is O(n^m) because of the recursive call stack.
Conclusion
Printing a given matrix in spiral form is one of the most interesting problems of Data structure. In this article, we have discussed two approaches to solve this problem. One is the naive approach, the next one is the recursive implementation of the naive approach. There are so many variations that can be made from this problem and this problem is most commonly asked during technical interviews. We hope this article will help you to understand the problem statement and you will be able to solve any other variation of this problem. Happy Coding!
People are also reading:
- Rod Cutting Problem – Dynamic Programming
- Program to Rotate an Array
- Construct a tree from Inorder and Level order traversals
- Write a C++ Program to print a Man using Graphics
- Program to Find LCM and HCF of two numbers
- Move all zeros present in an array to the end
- Longest Palindromic Subsequence using Dynamic Programming
- Find the maximum product of two integers in an array
- WAP to Count no. of alphabets, digits and spaces present in a file
- Find maximum of minimum for every window size in a given array
Leave a Comment on this Post