Data Structures & Algorithms in Java – Matrix – Spiral Matrix

Problem:

Given a matrix , collect the elements in the matrix in a spiral direction clockwise and return them as a list.

For example:

Consider the matrix [[1,2,3],[4,5,6],[7,8,9]]

You need to traverse the matrix spirally like below:

source : leetcode.com

So the output is :

[1,2,3,6,9,8,7,4,5]

Try out the solution here:

https://leetcode.com/problems/spiral-matrix/

Advertisements

Solution:

Hint:

Traverse right , then down , then left and finally up.

Do this until all the elements are traversed.

Approach 1: Traverse using pointers to the start row , start column and total number of rows and columns

In this approach we will use four major pointers.

Start Row

Start Column

Number of Rows

Number of Columns

Once you finish traversing one square in the spiral these values will change

For example,

After one round ,

Start Row will become 1

Start Column will become 1

No of Rows will be less by two (first row and last row will be ignored)

No of Columns will be less by two (first column and last column will be ignored)

You can continue traversing the squares until the number of columns or the number of rows becomes 0.

We need to consider two base conditions separately.

What if the square contains only one row or only one column.

Then you add all the elements in the row or column and return the list.

Here is the detailed algorithm:

STEP 1: Initialize four pointers , two for start of row and column , two for number of rows and columns.

STEP 2: While both number of rows and columns are non zero do the following:

STEP 2a: Check if there is only one row or column then return all the elements in a list

STEP 2b: Collect elements by traversing right leaving out the last element (last element will be picked in next step)

STEP 2c: Collect elements by traversing down leaving out the last element (last element will be picked in next step)

STEP 2d: Collect elements by traversing left leaving out the last element (last element will be picked in next step)

STEP 2e: Collect elements by traversing up

STEP 2f: Increment both start row and start column pointers and decrement number of rows and number of columns by two.

STEP 3: Return output.

Code:

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
        
        List<Integer> output = new ArrayList<Integer>();
        
        
        int startRow = 0;
        
        int startCol = 0;
        
        
        int noOfRows = matrix.length;
        int noOfCols = matrix[0].length;
        
        
        while(noOfCols > 0 && noOfRows > 0){
            
            
            int c = 0;
            int r = 0;
            
              if(noOfRows ==1 ){
                 
                 
                 for(int i=0;i<noOfCols;i++){
                     
                     output.add(matrix[startRow][startCol+i]);
                 }
                 break;
             }
            
            
             if(noOfCols ==1 ){
                 
                 
                 for(int i=0;i<noOfRows;i++){
                     
                     output.add(matrix[startRow+i][startCol]);
                 }
                 break;
             }
            
            
            while(c < noOfCols-1){
                
                output.add(matrix[r+startRow][c+startCol]);
             
                c++;
            }
   
            
            
            while(r < noOfRows-1){
                
                output.add(matrix[r+startRow][c+startCol]);
                
                
                r++;
            }
            
          
            
            
    
      
            while(c > 0){
                
                output.add(matrix[r+startRow][c+startCol]);
                c--;
                
            }
     
            while(r > 0){
                
                
                output.add(matrix[r+startRow][c+startCol]);
                
                r--;
            }
            noOfRows -= 2;
            noOfCols -= 2;
            startCol++;
            startRow++;
            
     
            
        }
      
        return output;
    }
}

The time complexity is O(m*n) where m is the number of rows and n the number of columns respectively.

Space complexity is also O(m*n) since we use a list whose size is in proportion to the input matrix.

This solution is fast as evident below in leetcode.com:

Advertisements

Approach2: Using pointers to start and end of rows and columns

The first approach was created by the author of this post .

The second approach discussed below got the most upvotes in leetcode discussions.

It uses four pointers : two to the start of rows and columns and two to the end of rows and columns.

These get adjusted as you traverse the matrix in a spiral way.

You traverse right and collect elements and then increment the start Row pointer

You traverse down and collect elements and then decrement the end Column pointer

You traverse left and collect elements and then decrement the end row pointer

You traverse up and collect elements and then increment the start column pointer

This way the outer square gets traversed and you are left with the start and end pointers to the inner square now.

Here is the algorithm:

ALGORITHM:

STEP 1: Initialize four pointers to the start and end of the rows and columns

STEP 2: While start row pointer is less than or equal to the end row pointer and start column pointer is less than or equal to the end column pointer do the following:

STEP 2a: Starting from the start column pointer to the end column pointer collect all elements and then increment the start row pointer

STEP 2b: Starting from the start row pointer to the end row pointer collect all elements and then decrement the end column pointer

STEP 2c: Starting from the end column pointer to the start column pointer collect all elements and decrement the row end pointer. Check if row start pointer is less than or equal to row end pointer before collecting the elements. The check should not be done for decrementing row end pointer.

STEP 2d: Starting from the row end pointer to the row start pointer collect all elements and increment the column pointer. Check if column start pointer is less than or equal to column end pointer before collecting the elements. The check should not be done for incrementing the column pointer.

STEP 3: Return the output.

Here is the code:

Code:

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
       List<Integer> output = new ArrayList<Integer>();
        if(matrix.length ==0) return output;
        
        
        int rowBegin = 0;
        
        int colBegin = 0;
        
        int rowEnd = matrix.length-1;
        
        int colEnd = matrix[0].length-1;
        
        
        while(rowBegin<= rowEnd && colBegin <=colEnd){
            
            
            
            //traverse right
            
            for(int i=colBegin;i<=colEnd;i++){
                
                
                output.add(matrix[rowBegin][i]);
                
                
            }
            
            rowBegin++;
            
            //traverse down
            
            for(int i=rowBegin;i<=rowEnd;i++){
                
                
                output.add(matrix[i][colEnd]);
                
            }
            colEnd--;
            //traverse left
            
            if(rowBegin<=rowEnd){
                
                
                for(int i=colEnd;i>=colBegin;i--){
                    
                    output.add(matrix[rowEnd][i]);
                }
                
            }
            
            rowEnd--;
            //traverse up
            
            if(colBegin <= colEnd){
                
                
                for(int i=rowEnd;i>=rowBegin;i--){
                    
                    
                    output.add(matrix[i][colBegin]);
                }
                
                
            }
            colBegin++;
            
        }
        return output;
        
    }
}

Time complexity is O(m * n ) where m is the number of rows and n the number of columns

Space complexity is also O(m * n ) since we collect all the elements in the matrix to a separate list of the same size.

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s