Problem Statement: Given a Matrix, print the given matrix in spiral order.
Examples:
Example 1:
Input: Matrix[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } }
Outhput: 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10.
Explanation: The output of matrix in spiral form.
Example 2:
Input: Matrix[][] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } }
Output: 1, 2, 3, 6, 9, 8, 7, 4, 5.
Explanation: The output of matrix in spiral form.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach:
Printing a matrix in spiral form is the same as peeling an onion layer by layer. Because we are printing the elements layer by layer starting from the outer layers.
In this approach, we will be using four loops to print all four sides of the matrix.
1st loop: This will print the elements from left to right.
2nd loop: This will print the elements from top to bottom.
3rd loop: This will print the elements from right to left.
4th loop: This will print the elements from bottom to top.
Steps:
- Create and initialize variables top as starting row index, bottom as ending row index left as starting column index, and right as ending column index. As shown in the image given below.
- In each outer loop traversal print the elements of a square in a clockwise manner.
- Print the top row, i.e. Print the elements of the top row from column index left to right and increase the count of the top so that it will move to the next row.
- Print the right column, i.e. Print the rightmost column from row index top to bottom and decrease the count of right.
- Print the bottom row, i.e. if top <= bottom, then print the elements of a bottom row from column right to left and decrease the count of bottom
- Print the left column, i.e. if left <= right, then print the elements of the left column from the bottom row to the top row and increase the count of left.
- Run a loop until all the squares of loops are printed.
Note: As we can see in the code snippet below, two edge conditions are being added in the last two ‘for’ loops: when we are moving from right to left and from bottom to top.
These conditions are added to check if the matrix is a single column or a single row. So, whenever the elements in a single row are traversed they cannot be traversed again backward so the condition is checked in the right-to-left loop. When a single column is present, the condition is checked in the bottom-to-top loop as elements from bottom to top cannot be traversed again.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
vector<int> printSpiral(vector<vector<int>> mat) {
// Define ans array to store the result.
vector<int> ans;
int n = mat.size(); // no. of nows
int m = mat[0].size(); // no. of columns
// Initialize the pointers reqd for traversal.
int top = 0, left = 0, bottom = n - 1, right = m - 1;
// Loop until all elements are not traversed.
while (top <= bottom && left <= right) {
// For moving left to right
for (int i = left; i <= right; i++)
ans.push_back(mat[top][i]);
top++;
// For moving top to bottom.
for (int i = top; i <= bottom; i++)
ans.push_back(mat[i][right]);
right--;
// For moving right to left.
if (top <= bottom) {
for (int i = right; i >= left; i--)
ans.push_back(mat[bottom][i]);
bottom--;
}
// For moving bottom to top.
if (left <= right) {
for (int i = bottom; i >= top; i--)
ans.push_back(mat[i][left]);
left++;
}
}
return ans;
}
int main() {
//Matrix initialization.
vector<vector<int>> mat {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
vector<int> ans = printSpiral(mat);
for(int i = 0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Time Complexity: O(m x n) { Since all the elements are being traversed once and there are total n x m elements ( m elements in each row and total n rows) so the time complexity will be O(n x m)}.
Space Complexity: O(n) { Extra Space used for storing traversal in the ans array }.
Java Code
import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<Integer> printSpiral(int[][] mat) {
// Define ans list to store the result.
List<Integer> ans = new ArrayList<>();
int n = mat.length; // no. of rows
int m = mat[0].length; // no. of columns
// Initialize the pointers required for traversal.
int top = 0, left = 0, bottom = n - 1, right = m - 1;
// Loop until all elements are not traversed.
while (top <= bottom && left <= right) {
// For moving left to right
for (int i = left; i <= right; i++)
ans.add(mat[top][i]);
top++;
// For moving top to bottom.
for (int i = top; i <= bottom; i++)
ans.add(mat[i][right]);
right--;
// For moving right to left.
if (top <= bottom) {
for (int i = right; i >= left; i--)
ans.add(mat[bottom][i]);
bottom--;
}
// For moving bottom to top.
if (left <= right) {
for (int i = bottom; i >= top; i--)
ans.add(mat[i][left]);
left++;
}
}
return ans;
}
public static void main(String[] args) {
//Matrix initialization.
int[][] mat = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
List<Integer> ans = printSpiral(mat);
for(int i = 0;i<ans.size();i++){
System.out.print(ans.get(i) + " ");
}
System.out.println();
}
}
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Time Complexity: O(m x n) { Since all the elements are being traversed once and there are total n x m elements ( m elements in each row and total n rows) so the time complexity will be O(n x m)}.
Space Complexity: O(n) { Extra Space used for storing traversal in the ans array }.
Python Code
def printSpiral(mat):
# Define ans array to store the result.
ans = []
n = len(mat) # no. of rows
m = len(mat[0]) # no. of columns
# Initialize the pointers reqd for traversal.
top = 0
left = 0
bottom = n - 1
right = m - 1
# Loop until all elements are not traversed.
while (top <= bottom and left <= right):
# For moving left to right
for i in range(left, right + 1):
ans.append(mat[top][i])
top += 1
# For moving top to bottom.
for i in range(top, bottom + 1):
ans.append(mat[i][right])
right -= 1
# For moving right to left.
if (top <= bottom):
for i in range(right, left - 1, -1):
ans.append(mat[bottom][i])
bottom -= 1
# For moving bottom to top.
if (left <= right):
for i in range(bottom, top - 1, -1):
ans.append(mat[i][left])
left += 1
return ans
#Matrix initialization.
mat = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
ans = printSpiral(mat)
print(ans)
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Time Complexity: O(m x n) { Since all the elements are being traversed once and there are total n x m elements ( m elements in each row and total n rows) so the time complexity will be O(n x m)}.
Space Complexity: O(n) { Extra Space used for storing traversal in the ans array }.
Javascript Code
// Define a function to print the matrix in a spiral order
function printSpiral(mat) {
// Define ans array to store the result.
let ans = [];
// Determine the number of rows and columns
let n = mat.length; // no. of rows
let m = mat[0].length; // no. of columns
// Initialize the pointers reqd for traversal.
let top = 0, left = 0, bottom = n - 1, right = m - 1;
// Loop until all elements are not traversed.
while (top <= bottom && left <= right) {
// For moving left to right
for (let i = left; i <= right; i++)
ans.push(mat[top][i]);
top++;
// For moving top to bottom.
for (let i = top; i <= bottom; i++)
ans.push(mat[i][right]);
right--;
// For moving right to left.
if (top <= bottom) {
for (let i = right; i >= left; i--)
ans.push(mat[bottom][i]);
bottom--;
}
// For moving bottom to top.
if (left <= right) {
for (let i = bottom; i >= top; i--)
ans.push(mat[i][left]);
left++;
}
}
return ans;
}
// Define the main function (not necessary in JavaScript)
// Matrix initialization.
let mat = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]];
let ans = printSpiral(mat);
for (let i = 0; i < ans.length; i++) {
console.log(ans[i] + " ");
}
console.log(); // Empty console.log() to print a newline
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Time Complexity: O(m x n) { Since all the elements are being traversed once and there are total n x m elements ( m elements in each row and total n rows) so the time complexity will be O(n x m)}.
Space Complexity: O(n) { Extra Space used for storing traversal in the ans array }.
Special thanks to Abhishek Yadav and Priyanshi Goel for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article