{x}
blog image

Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

 

Example 1:

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

Example 2:

Input: n = 1
Output: [[1]]

 

Constraints:

  • 1 <= n <= 20

Solution Explanation: Spiral Matrix II

This problem asks to generate an n x n matrix filled with numbers from 1 to n² in a spiral order. The solution uses a simulation approach.

Approach

The core idea is to simulate the spiral traversal. We use four directions (right, down, left, up) represented by dirs array in the code. We iterate through numbers from 1 to n², placing each number in the matrix according to the current spiral direction.

  1. Initialization: A n x n matrix ans is initialized with zeros. Variables i, j, and k track the current row, column, and direction, respectively. dirs array defines the direction changes (right: [0, 1], down: [1, 0], left: [0, -1], up: [-1, 0]).

  2. Iteration: The outer loop iterates from 1 to n². In each iteration:

    • The current number v is placed at ans[i][j].
    • The next position (x, y) is calculated based on the current direction k.
    • Boundary and Collision Check: If the next position (x, y) is out of bounds (less than 0 or greater than or equal to n) or already filled (ans[x][y] != 0), it means we've reached a boundary or completed a layer of the spiral. We change the direction k = (k + 1) % 4 (circularly moving through the directions).
    • The current position is updated to (x, y) based on the new (or unchanged) direction.

  3. Return: Finally, the generated spiral matrix ans is returned.

Time and Space Complexity Analysis

  • Time Complexity: The algorithm iterates through all n² elements of the matrix exactly once. Therefore, the time complexity is O(n²).

  • Space Complexity: The space complexity is dominated by the ans matrix, which has a size of n x n. Therefore, the space complexity is O(n²). The auxiliary variables (i, j, k, dirs) consume constant extra space, which is negligible compared to the matrix.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript)

The code examples in various languages provided in the original response directly implement the above approach. Each example demonstrates the same algorithm with minor syntax differences specific to each language. They all achieve a time complexity of O(n²) and a space complexity of O(n²).