# 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 n2 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:

```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:

```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:

```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

Written on May 9, 2013