Print a given matrix in spiral order

Difficulty: Medium, Asked-in: Amazon, Microsoft

Key takeaway: A good 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

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

Example 2

Input Matrix

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

  • An iterative approach using nested loops and variables
  • A recursive approach using decrease and conquer

An 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 pattern:

Observation 1: During the spiral traversal, horizontal and vertical boundaries are reducing by one. In other words, it is one row and column shorter than the boundaries of the previous segment.

Observation 2: Boundaries of each next segment starts in a cell adjacent to the cell where the previous segment ends.

The idea is to solve the problem by dividing the matrix into segments with horizontal and vertical boundaries. It is visible that elements in the outer segment are printed in a clockwise manner, and then we move to the next segment and print elements in a similar way. So, we can imagine each segment as four boundaries, namely 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 a nested loop for the implementation: an outer loop to traverse each matrix segment and four inner loops to print each element in the segments in a clockwise manner. After each iteration, we reduce the horizontal and vertical boundary size by 1 (Think!). 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

  1. We declare and initialize four variables to traverse matrix boundaries: rowStart = 0, , rowEnd = m - 1, colStart = 0, colEnd = n - 1.
  2. We run an outer loop to access each segment, where the loop will end when we reach the innermost segment. In other words, loop will run till rowStart < rowEnd and colStart < colEnd. Think! We start from the first segment.

    • We first print the top boundary from the colStart to the colEnd and increment the value of 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 the value of 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 the value of rowEnd to shift the bottom boundary to the next segment. Boundary condition: in the first step, we have increased the 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). Think!
    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 the value of colStart to shift the left boundary to the next segment. Boundary condition: in the second step, we have reduced the 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). Think!
    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 variables in such a way that we can repeat the same procedure for the inner loops.
  3. By end of the outer loop, our whole matrix gets printed in spiral order.

Solution Pseudocode

Time and space complexity analysis

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

A 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!

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)(n-2). We can use variables rowStart, colStart, rowEnd, and colEnd to track the matrix dimension during the recursion.

Solution Steps

We are using function printSpiralOrder(). Inside the function, we initialize all the variables and make a call to the helper unction 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 the recursiveSpiral(X[],rowStart, rowEnd, colStart, colEnd)

  • We first traverse the outermost boundary using four loops similar to the loop used in the iterative implementation. We also move to the next segment by updating the variables rowStart, colStart, rowEnd, and colEnd.
  • Now we print the remaining matrix recursively using the same function recursiveSpiral() with the updated boundary parameters i.e rowStart + 1, colStart + 1, rowEnd - 1, and colEnd - 1.
  • Base Condition: Recursion will stop in any one of the two conditions 1) When rowStart >= rowEnd or 2) colStart >= colEnd.

Solution Pseudocode

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 of analysis 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).

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)). Think

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 i.e. anticlockwise direction?
  • Try to explore the analysis of recursive solutions using the recursion tree method.

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

Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!

We welcome your comments

Subscribe Our Newsletter

Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.