# LeetCode Spiral Matrix I and II: Recursive and Iterative Index Calculation

## Overview

LeetCode Spiral Matrix I and II is to test array index manipulation which can be done in both recursive and iterative manner to find the pattern of calculation

## LeetCode Spiral Matrix I and II

(1)

Given a matrix of *m* x *n* elements (*m* rows, *n* columns), return all elements of the matrix in spiral order.

For example,

Given the following matrix:

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

You should return `[1,2,3,6,9,8,7,4,5]`

.

(2)

Given an integer *n*, generate a square matrix filled with elements from 1 to *n*^{2} in spiral order.

For example,

Given *n* = `3`

,

You should return the following matrix:

[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

## Analysis: Recursive and Iterative Index Calculation

Basically, this problem could be solved by bother recursive and iterative algorithm, just directly simulate the spiral pattern: top->right->bottom->left. And the following recursive implementation for Spiral Matrix I is accepted by LeetCode OJ:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
vector<int> ret;
void spiralOrderInner(const vector<vector<int>> matrix, int s, int m, int n) {
if (m < 1 || n < 1)
return;
if (m <= 1 || n <= 1) {
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ret.push_back(matrix[s + i][s + j]);
return ;
}
for (int i = s, endIndex = s + n - 2; i <= endIndex; ++i ) ret.push_back(matrix[s][i]);
for (int i = s, endIndex = s + m - 2; i <= endIndex; ++i ) ret.push_back(matrix[i][s + n - 1]);
for (int i = s + n - 1; i > s; --i ) ret.push_back(matrix[s + m - 1][i]);
for (int i = s + m - 1; i > s; --i ) ret.push_back(matrix[i][s]);
spiralOrderInner(matrix, s + 1, m - 2, n - 2);
}
vector<int> spiralOrder(vector<vector<int> > &matrix) {
ret.clear();
int m = matrix.size();
if (m < 1) return ret;
int n = matrix[0].size();
spiralOrderInner(matrix, 0, m, n);
return ret;
}
};

For the Spiral Matrix II, both of the following recursive and iterative implementation are accepted:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
void genInner(vector<vector<int>> &matrix, int k, int s, int len) {
if (1 == len) {
matrix[s][s] = k;
return ;
}
if (len <= 0) {
return ;
}
for (int i = 0; i < len; ++i) matrix[s][s + i] = k++;
for (int i = 1, col = s + len - 1; i < len; ++i) matrix[s + i][col] = k++;
for (int i = s + len - 2, row = s + len - 1; i >= s; --i) matrix[row][i] = k++;
for (int i = s + len - 2; i > s; --i) matrix[i][s] = k++;
genInner(matrix, k, s + 1, len - 2);
}
vector<vector<int> > generateMatrix(int n) {
vector<vector<int>> ret;
if (n < 1) return ret;
ret.resize(n);
for (int i = 0; i < n; ++i) ret[i].resize(n);
genInner(ret, 1, 0, n);
return ret;
}
};

And the following is the iterative one:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ret;
if (n < 1) return ret;
ret.resize(n);
for (int i = 0; i < n; ++i) ret[i].resize(n);
int i = 0, j = 0, k = 1, layer = 0;
int ns = n * n;
int direct = 0;
while (k <= ns) {
i = layer, j = layer;
while (j < n - layer) ret[i][j++] = k++;
i = layer + 1, j = n - layer - 1;
while (i < n - layer) ret[i++][j] = k++;
i = n - layer - 1, j = n - layer - 2;
while (j >= layer) ret[i][j--] = k++;
i = n - layer - 2, j = layer;
while (i > layer) ret[i--][j] = k++;
++layer;
}
return ret;
}

Further Reference: “Printing Matrix (2D array) in Spiral Order“.

## Summary

LeetCode Spiral Matrix I and II is to test array index manipulation which can be done in both recursive and iterative manner to find the pattern of calculation