Generate a Spiral Matrix

Implement generate_spiral_matrix(n: int) -> list[list[int]].

Return an n by n matrix containing every integer from 1 through n * n exactly once, arranged in clockwise spiral order. Start with 1 in the top-left cell, move right across the top boundary, and turn clockwise whenever the next cell would leave the current unfilled boundary.

Valid Input Domain

• n is a positive integer.

Constraints

• 1 <= n <= 1,000
• n * n fits in a signed 32-bit integer.

Public Examples

Example 1

Input: 3

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

Example 2

Input: 1

Output: [[1]]

Hint: Shrink four boundaries

After completing one side of the spiral, move the corresponding unfilled boundary inward.