# Spiral Order Matrix

## Problem Statement

Given a matrix A of size N X M. The task is to print the matrix in spiral order.

Examples:

Input: A[] = [[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]
Explanation: Shown in image

## Approach 1: Iterative

The idea is to traverse the given matrix in the following manner:

• Traverse left to right.
• Traverse top to bottom.
• Traverse right to left
• Traverse bottom to top

Continue these steps till all the elements have been visited.

Implementation of the Approach:

### C++ Code

```void spiralPrint(int m, int n, int a[R][C]) {
int i, k = 0, l = 0;

while (k &lt; m &amp;&amp; l &lt; n) {
for (i = l; i &lt; n; ++i) {
cout &lt;&lt; a[k][i] &lt;&lt; " ";
}
k++;
for (i = k; i &lt; m; ++i) {
cout &lt;&lt; a[i][n - 1] &lt;&lt; " ";
}
n--;
if (k &lt; m) {
for (i = n - 1; i &gt;= l; --i) {
cout &lt;&lt; a[m - 1][i] &lt;&lt; " ";
}
m--;
}
if (l &lt; n) {
for (i = m - 1; i &gt;= k; --i) {
cout &lt;&lt; a[i][l] &lt;&lt; " ";
}
l++;
}
}
}```

### Java Code

```static void spiralPrint(int m, int n, int a[][]) {
int i, k = 0, l = 0;

while (k &lt; m &amp;&amp; l &lt; n) {
for (i = l; i &lt; n; ++i) {
System.out.print(a[k][i] + " ");
}
k++;
for (i = k; i &lt; m; ++i) {
System.out.print(a[i][n - 1] + " ");
}
n--;
if (k &lt; m) {
for (i = n - 1; i &gt;= l; --i) {
System.out.print(a[m - 1][i] + " ");
}
m--;
}
if (l &lt; n) {
for (i = m - 1; i &gt;= k; --i) {
System.out.print(a[i][l] + " ");
}
l++;
}
}
}```

### Python Code

```def spiralPrint(m, n, a):
k = 0
l = 0

while k &lt; m and l &lt; n:
for i in range(l, n):
print(a[k][i], end=" ")

k += 1
for i in range(k, m):
print(a[i][n - 1], end=" ")

n -= 1
if k &lt; m:

for i in range(n - 1, (l - 1), -1):
print(a[m - 1][i], end=" ")

m -= 1

if l &lt; n:
for i in range(m - 1, k - 1, -1):
print(a[i][l], end=" ")

l += 1```
• Time Complexity: O(N * M), where N * M is the total size of the matrix
• Space Complexity: O(1), as no extra space is used.

## Approach 2: Recursive Solution

Similar to the last approach, we can try to solve this problem recursively. The idea of this approach is exactly similar to the iterative approach.

Algorithm:

• Consider four variables, i.e. starting_row, ending_row, starting_col, ending_col.
• Create a recursive function for printing the spiral matrix.
• Base cases would be: If the starting index of row/col is less than the size of row/col, then, terminate the function, else continue printing the boundary elements.
• Run a loop from left to right and print the element.
• Similarly, run a loop from top to bottom and right to left, and bottom to top.

Implementation of the Approach:

### C++ Code

```void print(int arr[R][C], int i, int j, int m, int n) {
if (i &gt;= m or j &gt;= n)
return;

for (int p = j; p &lt; n; p++)
cout &lt;&lt; arr[i][p] &lt;&lt; " ";

for (int p = i + 1; p &lt; m; p++)
cout &lt;&lt; arr[p][n - 1] &lt;&lt; " ";

if ((m - 1) != i)
for (int p = n - 2; p &gt;= j; p--)
cout &lt;&lt; arr[m - 1][p] &lt;&lt; " ";

if ((n - 1) != j)
for (int p = m - 2; p &gt; i; p--)
cout &lt;&lt; arr[p][j] &lt;&lt; " ";

print(arr, i + 1, j + 1, m - 1, n - 1);
}```

### Java Code

```static void print(int arr[][], int i, int j, int m,
int n) {
if (i &gt;= m || j &gt;= n) {
return;
}

for (int p = i; p &lt; n; p++) {
System.out.print(arr[i][p] + " ");
}

for (int p = i + 1; p &lt; m; p++) {
System.out.print(arr[p][n - 1] + " ");
}
if ((m - 1) != i) {
for (int p = n - 2; p &gt;= j; p--) {
System.out.print(arr[m - 1][p] + " ");
}
}
}```

### Python Code

```def printdata(arr, i, j, m, n):
if i &gt;= m or j &gt;= n:
return

for p in range(i, n):
print(arr[i][p], end=" ")

for p in range(i + 1, m):
print(arr[p][n - 1], end=" ")

if (m - 1) != i:
for p in range(n - 2, j - 1, -1):
print(arr[m - 1][p], end=" ")

if (n - 1) != j:
for p in range(m - 2, i, -1):
print(arr[p][j], end=" ")

printdata(arr, i + 1, j + 1, m - 1, n - 1)```
• Time Complexity: O(N * M), where N * M is the total size of the matrix
• Space Complexity: O(1), as no extra space is used.

## Practice Questions:

Spiral Order Matrix I

## FAQ

### Q.1: What is the time and space complexity of the recursive approach?

Ans: The time and space complexity of the recursive approach is O(N * M) and O(1).

### Q.2: How to traverse the matrix in an anti-clockwise direction?

Ans: The idea is the same. Just traverse the matrix from top to down, left to right, bottom to top and right to left.

##### Previous Post ## Depth First Search – Traversal Of The Graph

##### Next Post 