Spiral Matrix LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Intuit Microsoft Oracle Paytm VMware ZillowViews 10519

Problem Statement

Spiral Matrix Problem says In Spiral Matrix we want to print all the elements of a matrix in a spiral form in the clockwise direction.

Spiral Matrix LeetCode Solution

Spiral Matrix LeetCode Solution

 

Approach for Spiral Matrix:

Idea

The problem can be implemented by dividing the matrix into loops and printing all the elements in each loop one by one.

It can be observed that the elements of the outer loop are printed first in a clockwise direction then inner elements will be printed. In each movement we have four loops, first for loop iteration represents the movement from left to right, then the second for loop iteration represents from up to down, whereas the third loop iteration represents the movement from right to left and the fourth loop represents from bottom to top. In a similar fashion, we move for inner movements as well.

Algorithm

  • Create and initialize variables like rowstart, rowend,colstart, and colend.
  • rowstart and colstart represent the initial position of row and column respectively which initializes to zero.
  • rowend and colend represent the size of row and column respectively.
  • Run an outer while loop until all the elements will be printed and elements will be printed in a clockwise direction and in a spiral manner.
  • In each iteration of the outer loop, we traverse four inner loops which traverse from left to right, then traverse the last column from top to bottom, then traverse from right to left and the last inner loop traverse from bottom to top.

Code 

C++ Program for Spiral Matrix LeetCode Solution

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
       int m=matrix.size();
         vector<int>res;
          if(m==0)
          return res;
        int n=matrix[0].size();
        
        int rowstart=0;
        int rowend=m;
        int colstart=0;
        int colend=n;
        
        int k;
        
        while(rowstart<rowend && colstart<colend)
        {
          
            for(k=colstart;k<colend;k++)
            res.push_back(matrix[rowstart][k]);
            rowstart+=1;
            
            for(k=rowstart;k<rowend;k++)
            res.push_back(matrix[k][colend-1]);
            colend-=1;
            
            if(rowstart<rowend)
            {
                for(k=colend-1;k>=colstart;k--)
                res.push_back(matrix[rowend-1][k]);
                rowend-=1;
            }
            
            if(colstart<colend)
            {
                for(k=rowend-1;k>=rowstart;k--)
                res.push_back(matrix[k][colstart]);
                colstart+=1;
            }
            
        }
        return res;       
    }
};

 

Java Program for Spiral Matrix LeetCode Solution

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) 
    {
       int m=matrix.length;
          List<Integer>res=new ArrayList<>();
          if(m==0)
          return res;
        int n=matrix[0].length;
        
        int rowstart=0;
        int rowend=m;
        int colstart=0;
        int colend=n;
        
        int k;
        
        while(rowstart<rowend && colstart<colend)
        {
          
            for(k=colstart;k<colend;k++)
            res.add(matrix[rowstart][k]);
            rowstart+=1;
            
            for(k=rowstart;k<rowend;k++)
            res.add(matrix[k][colend-1]);
            colend-=1;
            
            if(rowstart<rowend)
            {
                for(k=colend-1;k>=colstart;k--)
                res.add(matrix[rowend-1][k]);
                rowend-=1;
            }
            
            if(colstart<colend)
            {
                for(k=rowend-1;k>=rowstart;k--)
                res.add(matrix[k][colstart]);
                colstart+=1;
            }
            
        }
        return res;   
    }
}

 

Complexity Analysis for Spiral Matrix LeetCode Solution

Time Complexity

Time Complexity of Spiral Matrix: O(m*n) whereas m and n represent the size of row and column respectively.

Space Complexity of Spiral Matrix: O(1) no extra space is used.

Reference: https://en.wikipedia.org/wiki/Spiral

Translate »