# Generate Spiral Matrix

## Problem

Given a positive integer $n$, generate a square matrix filled with elements from 1 to $n^2$ in spiral order.

Examples

Input: n = 4

Output:

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

## Solution

### Using 4 Variables for Traversal

In this problem, we can traverse the matrix layer by layer. A single layer traversal consists of -

• traversing from top left to top right (first row in the layer)
• traversing from top right to bottom right (last column in the layer)
• traversing from bottom right to bottom left (last row in the layer) and,
• traversing from bottom left to top left (first column in the layer)

One such example is shown below:

• traversing the first row in the layer

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

• traversing the last column in the layer

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

• traversing the last row in the layer

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

• traversing the first column in the layer

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

Thus, we can maintain 4 variables rowStart, rowEnd, columnStart and columnEnd. rowStart and columnStart are assigned to 0 and, rowEnd and columnEnd are assigned to n - 1. The variables are updated after each row and column traversal.

vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> matrix(n, vector<int>(n));
int rowStart = 0, rowEnd = n - 1, columnStart = 0, columnEnd = n - 1;
int cur = 1;
while (rowStart <= rowEnd and columnStart <= columnEnd) {
// traversing from top left to top right (first row in the layer)
for (int c = columnStart; c <= columnEnd; ++c) {
matrix[rowStart][c] = cur++;
}
++rowStart;
// traversing from top right to bottom right (last column in the layer)
for (int r = rowStart; r <= rowEnd; ++r) {
matrix[r][columnEnd] = cur++;
}
--columnEnd;
// traversing from bottom right to bottom left (last row in the layer)
for (int c = columnEnd; c >= columnStart; --c) {
matrix[rowEnd][c] = cur++;
}
--rowEnd;
// traversing from bottom left to top left (first column in the layer)
for (int r = rowEnd; r >= rowStart; --r) {
matrix[r][columnStart] = cur++;
}
++columnStart;
}
return matrix;
}

Time Complexity: $O(n^2)$

Space Complexity: $O(1)$