Spiral Order Matrix

Approaches

Now, let us discuss different approaches to solving this problem.

Iterative Approach

Let us discuss the first approach to this problem using the following image.

We can see that with each traversal in one direction, we decrease the length of the other row or column by one. With each complete cycle, we reduce the number of rows and columns by one. We repeat this process until all the blocks of the elements are reached.

We can solve this problem iteratively by traversing the matrix in the clockwise direction and reducing the number of columns and rows until we reach the last traversal.

We can take four main variables for it:

• rowstart:- It denotes the starting index of the row for current traversal.
   
• colstart:- It represents the starting index of the column for current traversal.
   
• rowend:- It denotes the ending index of the row for current traversal.
   
• colend:-  It represents the ending index of the column for current traversal.

We iterate through the matrix. In each iteration, we take four traversals in the following manner: left to right, top to bottom, right to left, and bottom to top. After each loop, we decrease and increase the value of the above variables accordingly.

Algorithm

The algorithm is as follows:

• Step 1: Initialize rowstart and colstart with 0, rowend with (number of rows-1), and colend with (number of columns-1). Also, initialize a variable counting the total number of visited blocks.
   
• Step 2: Create a while loop that runs until all the elements are visited by counting the variable of visited blocks. The total number of blocks is the product of the number of rows with the number of columns of the matrix.
   
• Step 3: Create four traversals inside the while loop. The first one goes through colstart to colend on the rowstart row. And then, we increase the index of rowstart by 1. We increase the number of visited blocks by 1 with each element’s traversal.
   
• Step 4: The second loop runs from rowstart to rowend on the colend column. And then, we decrease the index of colend by 1. We increase the number of visited blocks by 1 with each element’s traversal.
   
• Step 5: The third loop runs from colend to colstart on the rowend row. And then, we decrease the index of rowend by 1. We increase the number of visited blocks by 1 with each element’s traversal.
   
• Step 6: The fourth loop runs from rowend to rowstart on the colstart column. And then, we increase the index of colstart by 1. We increase the number of visited blocks by 1 with each element’s traversal.

We run these nested loops and get the result.

Implementation

Let us see the implementation of the algorithm as mentioned above in C++.

• C++

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
    vector<vector<int>> matrix{
        {1,2,3,4},
        {14,15,16,5},
        {13,20,17,6},
        {12,19,18,7},
        {11,10,9,8},
    };
        int r=matrix.size();
        int c=matrix[0].size();
        int count=0;
        int n=r*c;
        int rs=0;
        int cs=0;
        int re=r-1;
        int ce=c-1;
        while(count<n){
            for(int i=cs;i<=ce && count<n; i++){
                cout<<matrix[rs][i]<<" ";
                count+=1;
            }
            rs+=1;
            for(int i=rs;i<=re && count<n;i++){
                cout<<matrix[i][ce]<<" ";
                count+=1;
            }
            ce-=1;
            for(int i=ce;i>=cs && count<n;i--){
                cout<<matrix[re][i]<<" ";
                count+=1;
            }
            re-=1;
            for(int i=re;i>=rs && count<n;i--){
                cout<<matrix[i][cs]<<" ";
                count+=1;
            }
            cs+=1;
        }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

OUTPUT

We denote rowstart with rs, colstart with cs, rowend with re, and colend with ce. As we can see, the correct spiral order is our code output.

Time and Space Complexities

• Time Complexity: O(n x m)
  It is because there are two nested loops at a time. Here, n is the number of matrix rows, and m is the number of matrix columns.
   
• Space Complexity: O(1)
  It requires constant extra space.

Recursive Approach

Now that we have seen the iterative solution to the problem, we can implement it with recursion, too. We need to implement a recursive function following the same four-traversal approach. The only change is instead of now counting the number of visited blocks, we create the base case that the starting of the row and column must be lesser in number than the ending of the row and column, respectively, for each cycle. If this case is not accepted, then we have to return. Also, we have to check this case after every traversal. After one cycle of all four traversals, we call the recursive function again for the new smaller matrix. We can depict it using the following illustration:

As we can see, a new matrix is formed after one process of four traversals, and the recursive function is called until it hits the base condition.

Algorithm

The algorithm is as follows:

• Step 1: Create a recursive function taking the matrix, the rowstart, the rowend, the colstart, and the colend as the parameters.
   
• Step 2: Make the base case that if the index value of rowstart is greater than the index value of rowend; or if the index value of colstart is greater than colend's, the function should return immediately.
   
• Step 3: If the function passes through the base case, it should move towards the four traversals. The first one goes through colstart to colend on the rowstart row. And then, we increase the index of rowstart by 1. Recheck the base case.
   
• Step 4: The second loop runs from rowstart to rowend on the colend column. And then, we decrease the index of colend by 1. Recheck the base case.
   
• Step 5: The third loop runs from colend to colstart on the rowend row. And then, we decrease the index of rowend by 1. Recheck the base case.
   
• Step 6: The fourth loop runs from rowend to rowstart on the colstart column. And then, we increase the index of colstart by 1. Recheck the base case.
   
• Step 7: We call our recursive function again with the updated variable values.
   

Implementation

Let us see the implementation of the algorithm as mentioned above below in C++:

• C++

C++

#include <bits/stdc++.h>
using namespace std;

void solve(vector<vector<int>> matrix, int rs, int cs, int re, int ce){
    if(rs>re || cs>ce){
        return;
    }
    for(int i=cs;i<=ce; i++){
        cout<<matrix[rs][i]<<" ";
    }
    rs+=1;
    if(rs>re || cs>ce){
        return;
    }
    for(int i=rs;i<=re;i++){
        cout<<matrix[i][ce]<<" ";
    }
    ce-=1;
    if(rs>re || cs>ce){
        return;
    }
    for(int i=ce;i>=cs;i--){
        cout<<matrix[re][i]<<" ";
    }
    re-=1;
    if(rs>re || cs>ce){
        return;
    }
    for(int i=re;i>=rs;i--){
        cout<<matrix[i][cs]<<" ";
    }
    cs+=1;
    solve(matrix, rs, cs, re, ce);
}

int main() {
    vector<vector<int>> matrix{
        {1,2,3,4},
        {14,15,16,5},
        {13,20,17,6},
        {12,19,18,7},
        {11,10,9,8},
    };
    solve(matrix, 0, 0, matrix.size()-1, matrix[0].size()-1);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

OUTPUT

We denote rowstart with rs, colstart with cs, rowend with re, and colend with ce. As we can see, the correct spiral order is our code output.

Time and Space Complexities

• Time Complexity: O(n x m)
  Here, n is the number of rows, and m is the number of matrix columns. It is so because we iterate over every element of the matrix once.
   
• Space Complexity: O(min(n,m))
  It depends on the depth of the recursive stack. And, in each recursion cycle, the value of rows and columns decreases by 2. So, the recursion depends on the minimum of the number of rows and the number of columns.

Also see, Application of Graph in Data Structure

Frequently Asked Questions

What is a matrix?

A matrix is a type of data structure. It is basically a two-dimensional array that has rows and columns and data stored in it. It is an important type of data structure that is useful in many ways.

What is the Spiral Order Matrix problem?

The Spiral Order Matrix is a famous matrix problem. In this problem, we have to print the matrix elements in a spiral manner. The direction of the spiral can be clockwise or anticlockwise, as defined in the question.

What is the time and space complexity of the iterative approach for the Spiral Order Matrix problem?

The time complexity of the iterative approach for the Spiral Order Matrix problem is O(nxm). Here, n is the number of rows, and m is the number of matrix columns. The space complexity is O(1) since it requires constant extra space.

Conclusion

Matrix problems are asked frequently in technical interviews. It is an important data structure to study. Many kinds of problems can be built on matrices. One such famous problem is the Spiral Order Matrix. In this article, we learned what it is. Then, we implemented it using iterative and recursive methods with their codes and time and space complexities.

If you want to learn more, read the following articles:

• Print X'th element in the spiral form of a matrix
   
• Matrix in reverse Spiral Form
   
• Floyd's algorithm

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Codestudio. Also, you can enroll in our courses and check out the mock tests and problems available. Please check out our interview experiences and interview bundle for placement preparations. 

Happy Coding!