Code Implementation

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0]*n for _ in range(n)]
        left, right, top, bottom = 0, n-1, 0, n-1
        num = 1
        while left <= right and top <= bottom:
            for i in range(left, right+1):
                matrix[top][i] = num
                num += 1
            top += 1
            for i in range(top, bottom+1):
                matrix[i][right] = num
                num += 1
            right -= 1
            if top <= bottom:
                for i in range(right, left-1, -1):
                    matrix[bottom][i] = num
                    num += 1
                bottom -= 1
            if left <= right:
                for i in range(bottom, top-1, -1):
                    matrix[i][left] = num
                    num += 1
                left += 1
        return matrix
      

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        int num = 1;
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; ++i)
                matrix[top][i] = num++;
            ++top;
            for (int i = top; i <= bottom; ++i)
                matrix[i][right] = num++;
            --right;
            if (top <= bottom) {
                for (int i = right; i >= left; --i)
                    matrix[bottom][i] = num++;
                --bottom;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; --i)
                    matrix[i][left] = num++;
                ++left;
            }
        }
        return matrix;
    }
};
      

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

var generateMatrix = function(n) {
    const matrix = Array.from({length: n}, () => Array(n).fill(0));
    let left = 0, right = n - 1, top = 0, bottom = n - 1;
    let num = 1;
    while (left <= right && top <= bottom) {
        for (let i = left; i <= right; i++)
            matrix[top][i] = num++;
        top++;
        for (let i = top; i <= bottom; i++)
            matrix[i][right] = num++;
        right--;
        if (top <= bottom) {
            for (let i = right; i >= left; i--)
                matrix[bottom][i] = num++;
            bottom--;
        }
        if (left <= right) {
            for (let i = bottom; i >= top; i--)
                matrix[i][left] = num++;
            left++;
        }
    }
    return matrix;
};
      

Problem Description

The task is to generate an n x n square matrix filled with the numbers from 1 to n^2 in spiral order, starting from the top-left corner and proceeding clockwise. Each number must be placed exactly once, and each cell in the matrix must be filled. The result should be a valid matrix with no repeated or missing numbers.

• Input: An integer n representing the size of the matrix.
• Output: A 2D list (matrix) of size n x n filled in spiral order.
• There is only one valid solution for each n.
• Do not reuse or skip any numbers between 1 and n^2.

Thought Process

When approaching this problem, it's helpful to visualize how a spiral traversal works. Imagine writing numbers on a piece of paper, starting at the top-left, moving right until you hit the edge, then down, then left, then up, and so on, moving inwards in a spiral pattern.

A naive approach might be to simulate movement step by step, but that can get messy with direction changes and boundary checks. Instead, we can use four boundaries—top, bottom, left, and right—to keep track of the "frame" of the spiral. With each layer, we fill the top row, right column, bottom row, and left column, then move the boundaries inward.

The key insight is to systematically reduce the problem size by shrinking the boundaries after each loop, ensuring we don’t overwrite or skip any cells.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize the matrix: Create an n x n matrix filled with zeros (or any placeholder).
2. Set boundaries: Use four variables: left, right, top, and bottom to track the current edges of the spiral.
3. Start filling numbers: Initialize a counter num starting at 1. Loop until left <= right and top <= bottom.
   • Fill the top row from left to right.
   • Move top boundary down by 1.
   • Fill the right column from top to bottom.
   • Move right boundary left by 1.
   • If there are rows left, fill the bottom row from right to left, and move bottom up by 1.
   • If there are columns left, fill the left column from bottom to top, and move left right by 1.
4. Repeat: Continue the process until all numbers are filled.

This design ensures each number is placed exactly once, and the spiral order is maintained.

Example Walkthrough

Let's walk through an example with n = 3:

Our empty matrix:
[ [0, 0, 0],
[0, 0, 0],
[0, 0, 0] ]

• Fill top row: 1, 2, 3 → [1, 2, 3]
• Fill right column: 4, 5 → [1, 2, 3], [0, 0, 4], [0, 0, 5]
• Fill bottom row (right to left): 6, 7 → [1, 2, 3], [0, 0, 4], [7, 6, 5]
• Fill left column (bottom to top): 8 → [1, 2, 3], [8, 0, 4], [7, 6, 5]
• Fill center: 9 → [1, 2, 3], [8, 9, 4], [7, 6, 5]

Final matrix:
[ [1, 2, 3],
[8, 9, 4],
[7, 6, 5] ]

Time and Space Complexity

• Brute-force approach: If you tried to simulate each step with lots of direction and visited checks, complexity would still be O(n^2) for filling, but with more overhead for checks.
• Optimized approach (current): Each cell is filled exactly once, so the time complexity is O(n^2). There is no extra space beyond the output matrix, so space complexity is also O(n^2).

The algorithm is efficient and directly proportional to the size of the matrix.

Summary

In summary, the spiral matrix problem is elegantly solved by managing four boundaries and filling each side in turn, moving inward layer by layer. This systematic approach ensures each number is used once, the spiral order is maintained, and the code remains clean and efficient. The key insight is to reduce the problem size at each step by updating the boundaries, making the solution both intuitive and optimal for all n.