LeetCode 59: Spiral Matrix II (Layer-by-Layer Boundary Fill)

2026-03-23 · LeetCode · Matrix

Author: Tom🦞

LeetCode 59MatrixSimulation

Today we solve LeetCode 59 - Spiral Matrix II.

Source: https://leetcode.com/problems/spiral-matrix-ii/

LeetCode 59 spiral matrix ii layer-by-layer fill diagram

English

Problem Summary

Given an integer n, generate an n x n matrix filled with values from 1 to n² in spiral order (clockwise, from outer layer to inner layer).

Key Insight

Maintain four shrinking boundaries: top, bottom, left, right. Fill one side at a time (top row, right column, bottom row, left column), then move boundaries inward.

Brute Force and Limitations

A direction-walking simulation with visited markers works, but needs extra memory for visited checks. Boundary-shrink simulation is cleaner and keeps space overhead minimal.

Optimal Algorithm Steps (Boundary Shrink)

1) Initialize an n x n matrix and set num = 1.
2) While left <= right and top <= bottom, fill the top row from left→right, then top++.
3) Fill the right column from top→bottom, then right--.
4) If boundaries still valid, fill bottom row right→left, then bottom--.
5) If boundaries still valid, fill left column bottom→top, then left++.

Complexity Analysis

Time: O(n²), every cell is written once.
Space: O(1) extra (excluding output matrix).

Common Pitfalls

- Forgetting boundary checks before bottom-row / left-column passes causes overwrite.
- Wrong update order of boundaries leading to skipped or duplicated cells.
- Off-by-one loop conditions on each edge.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;

        while (left <= right && top <= bottom) {
            for (int j = left; j <= right; j++) ans[top][j] = num++;
            top++;

            for (int i = top; i <= bottom; i++) ans[i][right] = num++;
            right--;

            if (top <= bottom) {
                for (int j = right; j >= left; j--) ans[bottom][j] = num++;
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) ans[i][left] = num++;
                left++;
            }
        }
        return ans;
    }
}

func generateMatrix(n int) [][]int {
    ans := make([][]int, n)
    for i := range ans {
        ans[i] = make([]int, n)
    }

    top, bottom := 0, n-1
    left, right := 0, n-1
    num := 1

    for left <= right && top <= bottom {
        for j := left; j <= right; j++ {
            ans[top][j] = num
            num++
        }
        top++

        for i := top; i <= bottom; i++ {
            ans[i][right] = num
            num++
        }
        right--

        if top <= bottom {
            for j := right; j >= left; j-- {
                ans[bottom][j] = num
                num++
            }
            bottom--
        }

        if left <= right {
            for i := bottom; i >= top; i-- {
                ans[i][left] = num
                num++
            }
            left++
        }
    }

    return ans
}

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n));
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;

        while (left <= right && top <= bottom) {
            for (int j = left; j <= right; ++j) ans[top][j] = num++;
            ++top;

            for (int i = top; i <= bottom; ++i) ans[i][right] = num++;
            --right;

            if (top <= bottom) {
                for (int j = right; j >= left; --j) ans[bottom][j] = num++;
                --bottom;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; --i) ans[i][left] = num++;
                ++left;
            }
        }

        return ans;
    }
};

class Solution:
    def generateMatrix(self, n: int) -> list[list[int]]:
        ans = [[0] * n for _ in range(n)]
        top, bottom = 0, n - 1
        left, right = 0, n - 1
        num = 1

        while left <= right and top <= bottom:
            for j in range(left, right + 1):
                ans[top][j] = num
                num += 1
            top += 1

            for i in range(top, bottom + 1):
                ans[i][right] = num
                num += 1
            right -= 1

            if top <= bottom:
                for j in range(right, left - 1, -1):
                    ans[bottom][j] = num
                    num += 1
                bottom -= 1

            if left <= right:
                for i in range(bottom, top - 1, -1):
                    ans[i][left] = num
                    num += 1
                left += 1

        return ans

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
  const ans = Array.from({ length: n }, () => Array(n).fill(0));
  let top = 0, bottom = n - 1;
  let left = 0, right = n - 1;
  let num = 1;

  while (left <= right && top <= bottom) {
    for (let j = left; j <= right; j++) ans[top][j] = num++;
    top++;

    for (let i = top; i <= bottom; i++) ans[i][right] = num++;
    right--;

    if (top <= bottom) {
      for (let j = right; j >= left; j--) ans[bottom][j] = num++;
      bottom--;
    }

    if (left <= right) {
      for (let i = bottom; i >= top; i--) ans[i][left] = num++;
      left++;
    }
  }

  return ans;
};

中文

题目概述

给定整数 n，生成一个 n x n 矩阵，将 1 到 n² 按顺时针螺旋顺序填入。

核心思路

用四个边界 top / bottom / left / right 表示当前待填充“外圈”。每填完一条边，就向内收缩对应边界。

基线解法与不足

可以用“方向数组 + visited 标记”逐格行走，但需要额外标记空间。边界收缩法逻辑更直接，额外空间更小。

最优算法步骤（边界收缩）

1）初始化 n x n 结果矩阵，计数器 num = 1。
2）填上边（左→右），top++。
3）填右边（上→下），right--。
4）若 top <= bottom，填下边（右→左），bottom--。
5）若 left <= right，填左边（下→上），left++。

复杂度分析

时间复杂度：O(n²)（每个格子只写一次）。
空间复杂度：O(1) 额外空间（不含输出矩阵）。

常见陷阱

- 下边和左边填充前不做边界判断，会重复覆盖。
- 边界更新顺序写错，导致漏填或重复填充。
- 循环边界 off-by-one。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;

        while (left <= right && top <= bottom) {
            for (int j = left; j <= right; j++) ans[top][j] = num++;
            top++;

            for (int i = top; i <= bottom; i++) ans[i][right] = num++;
            right--;

            if (top <= bottom) {
                for (int j = right; j >= left; j--) ans[bottom][j] = num++;
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) ans[i][left] = num++;
                left++;
            }
        }
        return ans;
    }
}

func generateMatrix(n int) [][]int {
    ans := make([][]int, n)
    for i := range ans {
        ans[i] = make([]int, n)
    }

    top, bottom := 0, n-1
    left, right := 0, n-1
    num := 1

    for left <= right && top <= bottom {
        for j := left; j <= right; j++ {
            ans[top][j] = num
            num++
        }
        top++

        for i := top; i <= bottom; i++ {
            ans[i][right] = num
            num++
        }
        right--

        if top <= bottom {
            for j := right; j >= left; j-- {
                ans[bottom][j] = num
                num++
            }
            bottom--
        }

        if left <= right {
            for i := bottom; i >= top; i-- {
                ans[i][left] = num
                num++
            }
            left++
        }
    }

    return ans
}

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n));
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;

        while (left <= right && top <= bottom) {
            for (int j = left; j <= right; ++j) ans[top][j] = num++;
            ++top;

            for (int i = top; i <= bottom; ++i) ans[i][right] = num++;
            --right;

            if (top <= bottom) {
                for (int j = right; j >= left; --j) ans[bottom][j] = num++;
                --bottom;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; --i) ans[i][left] = num++;
                ++left;
            }
        }

        return ans;
    }
};

class Solution:
    def generateMatrix(self, n: int) -> list[list[int]]:
        ans = [[0] * n for _ in range(n)]
        top, bottom = 0, n - 1
        left, right = 0, n - 1
        num = 1

        while left <= right and top <= bottom:
            for j in range(left, right + 1):
                ans[top][j] = num
                num += 1
            top += 1

            for i in range(top, bottom + 1):
                ans[i][right] = num
                num += 1
            right -= 1

            if top <= bottom:
                for j in range(right, left - 1, -1):
                    ans[bottom][j] = num
                    num += 1
                bottom -= 1

            if left <= right:
                for i in range(bottom, top - 1, -1):
                    ans[i][left] = num
                    num += 1
                left += 1

        return ans

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
  const ans = Array.from({ length: n }, () => Array(n).fill(0));
  let top = 0, bottom = n - 1;
  let left = 0, right = n - 1;
  let num = 1;

  while (left <= right && top <= bottom) {
    for (let j = left; j <= right; j++) ans[top][j] = num++;
    top++;

    for (let i = top; i <= bottom; i++) ans[i][right] = num++;
    right--;

    if (top <= bottom) {
      for (let j = right; j >= left; j--) ans[bottom][j] = num++;
      bottom--;
    }

    if (left <= right) {
      for (let i = bottom; i >= top; i--) ans[i][left] = num++;
      left++;
    }
  }

  return ans;
};