Spiral Traversal of Matrix

Difficulty: Medium, Asked-in: Amazon, Microsoft.

Key takeaway: An excellent matrix problem to learn problem-solving using both iteration and recursion.

Let’s understand the problem

Given a 2-dimensional m x n matrix, print all the elements in spiral order.

Example 1

Input Matrix

Spiral Matrix Example 1

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

Example 2

Input Matrix

Spiral Matrix Example 2

Output: 1 2 3 4 5 6 12 18 24 23 22 21 20 19 13 7 8 9 10 11 17 16 15 14

Discussed solution approaches

Iterative approach using nested loops and variables
Recursive approach using decrease and conquer

Iterative approach using nested loops and variables

Solution idea

We can imagine the spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries. Here are two critical observations from the output:

After traversing the outer boundary in spiral order, horizontal and vertical boundaries will be reduced. It is two rows and two columns shorter than the boundaries of the previous segment.
Boundaries of each next segment start in a cell adjacent to the cell where the previous segment ends.

Spiral traversal of the matrix

So one idea is to solve the problem by dividing the matrix into segments with horizontal and vertical boundaries. Here we print elements in the outer segment in a clockwise manner and then move to the next segment and print elements in a similar way. So, we can imagine each segment as four boundaries: rowStart, colStart, rowEnd, and colEnd.

rowStart: start row of the matrix segment where we move from left to right.
colEnd: end column of the matrix segment where we move from top to down.
rowEnd: end row of the matrix segment where we move from right to left.
colStart: start column of the matrix segment where we move from down to up.

We can use nested loops: an outer loop to explore each matrix segment and four inner loops to print each element in the segments in a clockwise manner. After each iteration of the outer loop, we reduce the horizontal and vertical boundary size by 1. For example, after traversing the outermost segment, the boundaries of the next segment will be rowStart + 1, colEnd - 1, rowEnd -1, and colStart + 1.

Solution steps

Step 1: We declare and initialize four variables to traverse matrix boundaries: rowStart = 0, , rowEnd = m - 1, colStart = 0, colEnd = n - 1.

Step 2: We run an outer loop to access each segment and it will end when we reach the innermost segment. In other words, loop will run till rowStart <= rowEnd and colStart <= colEnd.

We first print the top boundary from colStart to colEnd and increment rowStart to shift the top boundary to the next segment.

for(int i = colStart; i <= colEnd; i = i + 1)
  print(X[rowStart][i])
          
rowStart = rowStart + 1

Now we print the right boundary from rowStart to rowEnd and decrement colEnd to shift the right boundary to the next segment.

for(int i = rowStart; i <= rowEnd; i = i + 1)
  print(X[i][colEnd])
          
colEnd = colEend - 1

Now we print the bottom boundary from colEnd to colStart and decrement rowEnd to shift the bottom boundary to the next segment. Boundary condition: After traversal of the top boundary, we increased rowStart by 1, so there can be a chance that the matrix segment will get reduced to one row i.e. both top and bottom boundaries are the same. So we only print the bottom boundary if(rowStart <= rowEnd).
```
if(rowStart <= rowEnd)
{
  for(int i = colEnd; i >= colStart; i = i - 1)
      print(X[rowEnd][i])
              
  rowEnd = rowEnd - 1
}
```
Finally, we print the left boundary from rowEnd to rowStart and increment colStart to shift the left boundary to the next segment. Boundary condition: After traversing the right boundary, we reduced colEnd by 1, so there can be a chance that the matrix segment will get reduced to one column i.e. both left and right boundaries are the same. So we only print the left boundary if(colStart <= colEnd).
```
if(colStart <= colEnd)
{
  for(int i = rowEnd; i >= rowStart; i = i - 1)
      print(X[i][colStart])
              
  colStart = colStart + 1
}
```
At this point, we have printed the outermost segment and updated the four boundaries for the next segment. So in the next iteration of the outer loop, it will traverse the next segment in spiral order.

Step 3: By end of the outer loop, our whole matrix gets printed in spiral order.

Solution pseudocode

void printSpiralOrder(int X[][], int m, int n)
{
    int rowStart = 0, rowEnd = m - 1 
    int colStart = 0, colEnd = n - 1 
    
    while(rowStart <= rowEnd && colStart <= colEnd)
    {
        for(int i = colStart; i <= colEnd; i = i + 1)
            print(X[rowStart][i])
        
        rowStart = rowStart + 1
        
        for(int i = rowStart; i <= rowEnd; i = i + 1)
            print(X[i][colEnd])
         
        colEnd = colEend - 1
        
        if(rowStart <= rowEnd)
        {
            for(int i = colEnd; i >= colStart; i = i - 1)
                print(X[rowEnd][i])
            
            rowEnd = rowEnd - 1
        }
        
        if(colStart <= colEnd)
        {
            for(int i = rowEnd; i >= rowStart; i = i - 1)
                print(X[i][colStart])
            
            colStart = colStart + 1
        }
    }
}

Time and space complexity analysis

We are traversing each element of the matrix once. Time complexity = O(n*m), Space complexity = O(1).

Recursive approach using decrease and conquer

Solution idea

Can we think to solve this problem recursively? The idea is to visualize the problem solution via the solution of the smaller problem. Let's think!

Spiral matrix solution using recursion

Suppose we have a given matrix of dimension m x n to print in the spiral order. After printing the outermost boundary using four loops, now the problem gets reduced to a smaller version of the same problem: Printing the inner matrix of dimension (m-2)x(n-2). We can use variables rowStart, colStart, rowEnd, and colEnd to track the matrix dimension during the recursion.

Solution steps

Suppose we are using function printSpiralOrder(). Inside the function, we initialize all the variables and make a call to the helper function recursiveSpiral() to print the matrix in spiral order.

void printSpiralOrder(int X[][], int m, int n)
{
    int rowStart = 0, rowEnd = m - 1 
    int colStart = 0, colEnd = n - 1 
    recursiveSpiral(X, rowStart, rowEnd, colStart, colEnd)
}

Implementation of recursiveSpiral(X[], rowStart, rowEnd, colStart, colEnd)

Step 1: We first traverse the outermost boundary using four loops similar to the loop used in the iterative implementation.

Print the first row from colStart to colEnd.
Print the last column from rowStart + 1 to rowEnd.
Print the last row from colEnd - 1 to colStart. Before doing this, we need to check if the last and the first row are not the same.
Print the first column from rowEnd - 1 to rowStart + 1. Before doing this, we need to check if the last and the first column are not the same.

Step2: Now we print the remaining matrix recursively using the same function with the updated boundary parameters i.e rowStart + 1, colStart + 1, rowEnd - 1, and colEnd - 1.

Base condition: Recursion will stop when rowStart > rowEnd or colStart > colEnd.

Solution pseudocode

void recursiveSpiral(int X[][], int rowStart, int rowEnd, int colStart, int colEnd)
{
    if(rowStart > rowEnd || colStart > colEnd)
        return
    
    for(int i = colStart; i <= colEnd; i = i + 1)
        print(X[rowStart][i])
        
    for(int i = rowStart + 1; i <= rowEnd; i = i + 1)
        print(X[i][colEnd])
        
    if(rowEnd != rowStart)
    {
        for(int i = colEnd - 1; i >= colStart; i = i - 1)
            print(X[rowEnd][i])
    }
        
    if(colEnd != colStart)
    {
        for(int i = rowEnd - 1; i >= rowStart + 1; i = i - 1)
            print(X[i][colStart])
    }
    
    recursiveSpiral(X, rowStart + 1, rowEnd - 1, colStart + 1, colEnd - 1)
}

Time and space complexity analysis

In the above solution, there is no need to do analysis by writing recurrence relation and solving it using the recursion tree method! The idea would be simple: We are printing each element of the matrix and performing an O(1) operation for each element. So time complexity = m*n*O(1) = O(mn).

Space complexity depends on the size of the call stack which is equal to the depth of the recursion. Here input size is decreasing by the factor of 2 at each step of recursion i.e both m and n are decreasing by 2. So the depth of the recursion depends on the minimum of m and n.

If m > n, depth of the recursion = n/2.
If m < n, depth of the recursion = m/2.

So space complexity = O(min(m, n)).

Critical ideas to think!

Explain the boundary situation when there is a single row or single column in the matrix. Before running last two inner loops, Why are we checking the condition if(rowStart < rowEnd) and if(colStart < colEnd)?
Can we solve this problem using some other approach?
How do we modify the logic if we need to print the matrix in reverse spiral order?

Comparisons of time and space complexities

Using iterative approach: Time = O(mn), Space = O(1).
Using recursive approach: Time = O(mn), Space = O(max(m, n).

Matrix-based problems to practice

Rotate a matrix by 90 degrees
Find row with max ones
Transpose matrix
Set matrix zeroes
01 Matrix
Reshape the matrix

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!

Print a Given Matrix in Spiral Form

Let’s understand the problem

Example 1

Example 2

Discussed solution approaches

Iterative approach using nested loops and variables

Solution idea

Solution steps

Solution pseudocode

Time and space complexity analysis

Recursive approach using decrease and conquer

Solution idea

Solution steps

Solution pseudocode

Time and space complexity analysis

Critical ideas to think!

Comparisons of time and space complexities

Matrix-based problems to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs