Difficulty: Medium, Asked-in: Amazon, Microsoft
Key takeaway: A good matrix problem to learn problem-solving using both iteration and recursion.
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
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.
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
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.
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
}
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)
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)
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.
So space complexity = O(min(m, n)). Think
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!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.