Print a given matrix in spiral form

Difficulty: Medium, Asked In: Amazon, Microsoft

Two solutions discussed

1. Using iterative approach — Using nested loops and variables
2. Using recursive approach — Decrease and conquer approach

Key takeaway after reading this blog

This is an excellent matrix problem for learning problem-solving using both iteration and recursion. The time complexity of both approaches is the same.

Let’s understand the problem

Given a 2-dimensional array, print the elements in spiral order. Let’s see an illustration to see how spiral order traversal looks like:

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

Solution 1: Iterative approach

Algorithm Idea

We can imagine that the spiral consists of an ordered set of boundaries or horizontal and vertical segments.

Observation 1: Each next boundary or segment is one size shorter than the previous segment, and the same goes for vertical segments.

Observation 2: Each next segment starts in a cell that is adjacent to the cell where the previous segment ends.

The problem can be solved by dividing the matrix into boundaries. It is visible that elements of the outer loop are printed in a clockwise manner, and then the elements from the inner loop are printed. So, we can imagine the outer loop as four boundaries, namely row_start, col_start, row_end, and col_end.

• row_start: path of the matrix where we move from left to right.
• row_end: path of the matrix where we move from right to left.
• col_start: path of the matrix where we move from up to down.
• col_end: path of the matrix where we move from down to up.

We print elements covered by each boundary in a clockwise manner using four loops, and after each iteration, reduce the dimension of the boundary to form an inner loop of the matrix. Now, the new boundary conditions become our new matrix.

Algorithm Steps

1. Initialize four variables as row_start, row_end, col_start, col_end.
2. Run a loop until all the elements are printed.

• Print the top row from col_start to col_end, then increment the value of row_start to shift the top boundary by one down.
• Print the rightmost column from row_start to row_end and shift the right boundary one left by decrementing the value of col_end.
• Print the bottom row from col_end to col_start, and shift the bottom boundary one row up by decrementing the value of row_end.
• Print the leftmost column from row_end to row_start and increment the value of col_start to shift the leftmost boundary one right.

At this point, we have printed our outer loop and reduced the variables in such a way that it now repeats the same procedure for the inner loops.

Algorithm Code C++

void spiral_matrix(int n, int m) 
{
    int row_start = 0, col_start = 0, row_end = n, col_end = m;

    while (row_start < row_end && col_start < col_end) 
    {
        // Print the top row from left to right
        for (int i = col_start; i < col_end; i++)
            cout << mat[row_start][i] << " ";

        row_start++;

        // Print the rightmost column from top to bottom
        for (int i = row_start; i < row_end; i++) 
            cout << mat[i][col_end - 1] << " ";

        col_end--;

        // Print the bottom row from right to left
        if (row_start < row_end) 
        {
            for (int i = col_end - 1; i >= col_start; i--) 
                cout << mat[row_end - 1][i] << " ";

            row_end--;
        }

        // Print the leftmost column from bottom to top
        if (col_start < col_end) 
        {
            for (int i = row_end - 1; i >= row_start; i--) 
                cout << mat[i][col_start] << " ";

            col_start++;
        }
    }
}

Algorithm Analysis

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

Possible questions by the Interviewer

• Explain the boundary situations when there is a single row or a single column in the matrix.
• How do we modify the logic if we need to print the matrix in reverse spiral order, i.e., in the anticlockwise direction?
• Why do we check the conditions if(row_start < row_end) and if(col_start < col_end) before running the last two inner loops?
• Is it possible to solve this problem using recursion?

Solution 2: Recursive approach

Algorithm Idea

We can solve this problem using recursion. The main idea is that in each recursive call, we move from the outer loop to the inner loop by reducing the boundary dimensions and solving the smaller version of the problem.

Suppose we have a matrix of size R x C that needs to be traversed in spiral order. After traversing the boundary in a spiral order using four loops, the problem is reduced to a smaller version of the same problem — traversing the inner matrix of size (R-2) x (C-2). We can use the variables row_start, col_start, row_end, and col_end to keep track of the matrix dimensions during recursion.

Algorithm Code C++

void spiral_matrix(int row_start, int col_start, int row_end, int col_end) 
{
    // Base case
    if (row_start >= row_end || col_start >= col_end)
        return;

    // Print First Row
    for (int i = col_start; i < col_end; i++)
        cout << mat[row_start][i] << " ";
    
    // Print Last Column
    for (int i = row_start + 1; i < row_end; i++)
        cout << mat[i][col_end - 1] << " ";

    // Print Last Row, if Last and First Row are not same
    if ((row_end - 1) != row_start) 
    {
        for (int i = col_end - 2; i >= col_start; i--)
            cout << mat[row_end - 1][i] << " ";
    }

    // Print First Column, if Last and First Column are not same
    if ((col_end - 1) != col_start) 
    {
        for (int i = row_end - 2; i > row_start; i--)
            cout << mat[i][col_start] << " ";
    }

    spiral_matrix(row_start + 1, col_start + 1, row_end - 1, col_end - 1);
}

Algorithm Analysis

We are exploring each matrix element only once and doing O(1) operation for each element. So time complexity = m*n*O(1) = O(mn).

This is a recursive program. So space complexity is equal to the size of the call stack which is equal to the max depth of the recursion. Here 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!

Reviewer: Shubham Gautam

Matrix-based problems to practice

• Rotate a matrix by 90 degrees
• Find row with max ones
• Search in a row wise and column wise sorted matrix
• Count zeros in a row-wise and column-wise sorted matrix

Suggested concept blogs to explore

• DSA Problem Solving Steps
• DSA Problem Solving Techniques
• DSA Interview Guide
• Time Complexity Analysis
• Fundamentals of Iteration
• Analysis of Loop and Iteration
• Recursion vs. Iteration

For more content, explore our free DSA course and coding interview blogs.

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

Originally published at https://www.enjoyalgorithms.com/blog/print-matrix-in-spiral-order/.