56. Spiral Matrix II

Keep four shrinking boundaries — top, bottom, left, right. Fill the top row left-to-right, the right column top-to-bottom, the bottom row right-to-left, the left column bottom-to-top, then move the boundaries inward. A running counter supplies the values 1..n^2.

Walk the perimeter, then shrink

Maintain four walls: top, bottom, left, right, and a counter v starting at 1. Repeatedly trace the current outer ring in spiral order and pull the walls inward:

top, bottom, left, right = 0, n-1, 0, n-1; v = 1
while top <= bottom and left <= right:
    for j in left..right:      m[top][j]   = v++   ; top++
    for i in top..bottom:      m[i][right]  = v++   ; right--
    if top <= bottom:
        for j in right..left:  m[bottom][j] = v++   ; bottom--
    if left <= right:
        for i in bottom..top:  m[i][left]   = v++   ; left++
return m

The two if guards prevent re-filling a middle row/column when the remaining region is a single line.

Worked example

n = 3:

• Top row L→R: 1 2 3.
• Right col T→B: 4, then 5.
• Bottom row R→L: 6, 7.
• Left col B→T: 8.
• Center: 9.

Result:

1 2 3
8 9 4
7 6 5

Complexity

• Time: O(n^2) — each cell filled once.
• Space: O(1) beyond the output matrix.

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] m = new int[n][n];
        int top = 0, bottom = n - 1, left = 0, right = n - 1, v = 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) m[top][j] = v++;
            top++;
            for (int i = top; i <= bottom; i++) m[i][right] = v++;
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) m[bottom][j] = v++;
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) m[i][left] = v++;
                left++;
            }
        }
        return m;
    }
}