Difficulty: Medium, Asked-in: Amazon, Microsoft.
Key takeaway: An excellent 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.
Input Matrix
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
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
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:
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.
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.
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
}
Step 3: By end of the outer loop, our whole matrix gets printed in spiral order.
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
}
}
}
We are traversing each element of the matrix once. Time complexity = O(n*m), Space complexity = O(1).
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)x(n-2). We can use variables rowStart, colStart, rowEnd, and colEnd to track the matrix dimension during the recursion.
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.
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.
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)
}
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.
So space complexity = O(min(m, n)).
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!