What Is Print Spiral Matrix?

What Is Print Spiral Matrix?
What Is Print Spiral Matrix?

Introduction

Wherever you go through an interview, it is rare to know that there is no question asked on arrays, and as arrays are categorised into three types, basically as:

  • One dimensional array
  • Two-dimensional arrays
  • Multidimensional arrays 

So, today we will be discussing one of the most asked questions in interviews based on 2-D arrays- “Print Spiral Matrix.”

Problem Statement- You are given a 2-D array ‘MATRIX’ of dimensions N x M, of integers. You need to print the matrix in a spiral fashion (clockwise). 


“Here ‘N’ denotes the number of rows whereas ‘M’ denotes the number of columns.”

Example: 

This is how a spiral matrix would look like:

How will we get the required output?

  • Start moving from the first element of row1 towards the right and print all the elements of row one, i.e., 1 2 3 4.
  • Now, move towards a downward direction in the last column, i.e. column 4, and print the elements as 5,6,7.
  • Now, move towards the left in the last row, i.e. row 4, and again print all its elements as 8,9,10.
  • This time we will be moving in an upward direction in the first column and print the elements 11,12.
  • Again move in the right direction in the second row and print the elements as 13.
  • Next moving down in three columns and simply print 15.
  • At last, towards the left and print the elements of the third row as 16.

Now, without any delay, let’s head on to the solution.

Before that, it would be great if you give it a try by yourself Here. There can be several ways to print a spiral matrix, so we will discuss all of them, starting with the Brute force approach.

Method 1: (Brute Force – Simulation-based) 

The idea is basically to draw the path that the spiral will create, knowing the fact that the path will turn in a clockwise direction if it goes beyond the range or into a cell that was already visited.

Algorithm

  • The matrix will have R*C elements.
  • We will take a vector to know which cell has already been visited.
  • Assuming that the current visited cell is some (row, col) facing some direction dir.
  • And now the next cell to be visited by some (nr,nc).
  • This would be the next position if it is within the bounds or has not been visited.
  • If this doesn’t act to be the next position, then the one that will appear after changing the direction will be the next position.

To make it more clear below is the C++ code. You can consider it.

Code:

#include <bits/stdc++.h>
using namespace std;
 
vector<int> printSpiral(vector<vector<int> >& mat)
{
    vector<int> output;
 //if the size gets 0, then simply return the vector formed so far
    if (mat.size() == 0)
        return output;
 
    int R = mat.size(), C = mat[0].size();
    vector<vector<bool> > visited(R, vector<bool>(C, false));
    int drow[] = { 0, 1, 0, -1 };
    int dcol[] = { 1, 0, -1, 0 };
    int row = 0, col = 0, dir = 0;
 
    // Iterate from 0 to R * C - 1
    for (int i = 0; i < R * C; i++) {
        output.push_back(mat[row]);
        visited[row] = true;
        int nr = row + drow[dir];
        int nc = col + dcol[dir];
 
        if (0 <= nr && nr < R && 0 <= nc && nc < C
            && !visited[nr][nc]) {
            row = nr;
            col = nc;
        }
        else {
        //as one of the rows or column is printed, the direction will be
        //changed so increment by 1
            dir = (dir + 1) % 4;
            row += drow[dir];
            col += dcol[dir];
        }
    }
    return output;
}
 
// Driver code
int main()
{
    vector<vector<int> > arr{ { 1, 2, 3, 4 },
                            { 12, 13, 14, 5 },
                            { 11, 16, 15, 6 },
                            { 10, 9, 8, 7 } };
 
    for (int i : printSpiral(arr)) {
        cout << i << " ";
    }
    return 0;
}

Output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Time Complexity: O(r*c)

  • Since every element of the matrix will be traversed the time complexity will be O(r*c).

Space Complexity: O(r*c)

  • Extra space is occupied as we make use of vectors, so it will take space equivalent to the count of elements present in the matrix.

Method 2: (Optimised Approach)

Use different if-else conditions to know in which row or column you need to move and in which direction and print the elements associated with it.

Algorithm

  • Take four variables to iterate through the rows and columns.
  • Now, once you have covered a row or column it’s pretty clear that the direction needs to be changed so for that also take a variable to make the direction change.
  • Now just go through a loop while all the rows and columns are traversed.
  • Keep on checking the conditions that now which direction we need to move.
  • And simply keep on printing the elements.

Below mentioned is the C++ code, which will help you get things more clear.

Code

#include <bits/stdc++.h>
using namespace std;
void spirallytraverse(int matrix[4][4], int r, int c) 
{//initialize variables
        int top=0;
        int bottom=r-1;
        int left=0;
        int right=c-1;
        int direction=0;
        //run the loop until every row and column is traversed
        while(left<=right&&top<=bottom)
        {
            if(direction==0)
            {
                for(int i=left;i<=right;i++)
                {
                    cout<<matrix[top][i]<<" ";
                }top++;
            }
            else if(direction==1)
            {
                for(int i=top;i<=bottom;i++)
                {
                    cout<<matrix[i][right]<<" ";
                }right--;
            }
            else if(direction==2)
            {
                for(int i=right;i>=left;i--)
                {
                    cout<<matrix[bottom][i]<<" ";
                }bottom--;
            }
            else if(direction==3)
            {
                for(int i=bottom;i>=top;i--)
                {
                    cout<<matrix[i][left]<<" ";
                }left++;
            }
            direction=(direction+1)%4;
        }
}
int main()
{ int matrix[4][4]={{1, 2, 3 ,4},
                    {12, 13, 14, 5},
                    {11, 16, 15, 6},
                     {10, 9, 8, 7}};
    spirallytraverse(matrix,4,4);                 
    return 0;
}

Output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Time complexity: O(r*c)

  •  The traversal of the matrix will acquire the time of order r*c, that is, rows*columns.

Space Complexity: O(1)

  • No extra space is required so space complexity will be constant.

Method 3: (Using Recursion)

The idea is simple, as we were making changes in the direction after every traversal in the previous method here, we will make the call recursive once the direction gets changed.

Algorithm

  • Pass all the variables we took in the earlier method as left, right, top, bottom to the function.
  • Check if the left is less than the right.
  • Print the 1-row elements and make the top move to the next row.
  • Now, check if the top is less than the bottom or not.
  • If yes, then simply print the last column that is the 4th column in the example.
  • Now, check if the left is less than right or not.
  • If yes, print the elements of the 4th row.
  • Again, check if the top is less than the bottom. If yes, then print the elements of 1 column.
  • Now, one cycle is completed, so we will call the function again until it reaches the bounds.

To get it more clear, we first suggest to dry run using pen and paper, and then you can take help from below mentioned code.

Code:

#include <iostream>
using namespace std;
 
void printSpiral(int mat[4][4], int top, int bottom, int left, int right)
{
    //bound exceeds
    if (left > right) {
        return;
    }

    //print top row
    for (int i = left; i <= right; i++) {
        cout << mat[top][i] << " ";
    }
    top++;
    if (top > bottom) {
        return;
    }

    // print right column
    for (int i = top; i <= bottom; i++) {
        cout << mat[i][right] << " ";
    }
    right--;
    if (left > right) {
        return;
    }

    // print bottom row
    for (int i = right; i >= left; i--) {
        cout << mat[bottom][i] << " ";
    }
    bottom--;
    if (top > bottom) {
        return;
    }

    // print left column
    for (int i = bottom; i >= top; i--) {
        cout << mat[i][left] << " ";
    }
    left++;

    //one direction is over move to next using a recursive call
    printSpiral(mat, top, bottom, left, right);
 
}
 
int main()
{
    int mat[4][4] =
    {
        { 1, 2, 3, 4},
        {12, 13, 14, 5},
        {11, 16, 15, 6},
        {10, 9, 8, 7}
    };
 
    int top = 0, bottom = 4 - 1;
    int left = 0, right = 4 - 1;
    printSpiral(mat, top, bottom, left, right);
    return 0;
}

Output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Time Complexity: O(r*c)

  • All the elements of the matrix will be traversed so the complexity will be O(r*c).

Space Complexity: O(r*c)

  • The space complexity will be of order (r*c) as space will be occupied in the stack due to recursion.

Frequently Asked Questions

What is a spiral array?

It is an arrangement of first (n square) elements in a square fashion where, as we go around the edges, the number goes on increasing sequentially, and the array moves spirally inwards.

How do you traverse an array in a spiral?

As discussed in the method to print a spiral matrix, we can traverse any array in spiral form by taking four different variables each at initial row, final row, initial column, final column and take one variable to address the change in direction.

What is a two-dimensional array?

It is similar to a 1-D array but can be visualised as a table with rows and columns.

How to print a matrix in spiral order?

There can be several methods, as discussed above, to print a matrix in spiral order ranging from, one which can be done through traversing the matrix, or you can do it using recursion.

Key Takeaways

The main idea behind solving the problem, “print spiral matrix,” is traversing through the matrix in such a way that at a time, we print a complete row or column and then change the direction and repeat the same for the rest of the elements.

It would be great if this problem is clear to you, champ. But don’t give it up here. Bang on to solve some of the highly recommended interview questions and keep on growing.

Don’t forget to test yourself by solving the problems on CodeStudio.

Keep exploring, keep growing!

By Neerulata

Exit mobile version