Spiral Matrix II

medium array matrix simulation

Problem

Given a positive integer n, generate an n × n matrix filled with the integers 1 to n² in spiral order.

Inputn = 3

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

Walk right across row 0, down the last column, left across the last row, up the first column, and shrink inward.

def generate_matrix(n):
    m = [[0] * n for _ in range(n)]
    top, bottom, left, right = 0, n - 1, 0, n - 1
    val = 1
    while val <= n * n:
        for c in range(left, right + 1):
            m[top][c] = val; val += 1
        top += 1
        for r in range(top, bottom + 1):
            m[r][right] = val; val += 1
        right -= 1
        for c in range(right, left - 1, -1):
            m[bottom][c] = val; val += 1
        bottom -= 1
        for r in range(bottom, top - 1, -1):
            m[r][left] = val; val += 1
        left += 1
    return m

function generateMatrix(n) {
  const m = Array.from({ length: n }, () => new Array(n).fill(0));
  let top = 0, bottom = n - 1, left = 0, right = n - 1;
  let val = 1;
  while (val <= n * n) {
    for (let c = left; c <= right; c++) m[top][c] = val++;
    top++;
    for (let r = top; r <= bottom; r++) m[r][right] = val++;
    right--;
    for (let c = right; c >= left; c--) m[bottom][c] = val++;
    bottom--;
    for (let r = bottom; r >= top; r--) m[r][left] = val++;
    left++;
  }
  return m;
}

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] m = new int[n][n];
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int val = 1;
        while (val <= n * n) {
            for (int c = left; c <= right; c++) m[top][c] = val++;
            top++;
            for (int r = top; r <= bottom; r++) m[r][right] = val++;
            right--;
            for (int c = right; c >= left; c--) m[bottom][c] = val++;
            bottom--;
            for (int r = bottom; r >= top; r--) m[r][left] = val++;
            left++;
        }
        return m;
    }
}

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> m(n, vector<int>(n, 0));
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    int val = 1;
    while (val <= n * n) {
        for (int c = left; c <= right; c++) m[top][c] = val++;
        top++;
        for (int r = top; r <= bottom; r++) m[r][right] = val++;
        right--;
        for (int c = right; c >= left; c--) m[bottom][c] = val++;
        bottom--;
        for (int r = bottom; r >= top; r--) m[r][left] = val++;
        left++;
    }
    return m;
}

Explanation

We fill an n × n grid with 1 through n² by literally walking the spiral: across the top, down the right side, back across the bottom, up the left, then spiral inward. The clean way to control this is with four boundary lines.

We keep top, bottom, left, and right marking the edges of the part we still need to fill, plus a counter val that starts at 1.

Each loop does four passes. Go right along the top row, then move top down. Go down the right column, then move right in. Go left along the bottom row, then move bottom up. Go up the left column, then move left in. After every cell we write the current val and increment it.

Shrinking the boundaries after each pass is what makes the path coil inward and never overwrite a filled cell. We stop once val exceeds n².

Example: for n = 3 we write 1,2,3 across the top, 4,5 down the right, 6,7 across the bottom, 8 up the left, and finally 9 in the center, giving [[1,2,3],[8,9,4],[7,6,5]].

Time: O(n²) Space: O(1)