title: Spiral Matrix II
slug: spiral-matrix-ii
difficulty: medium
leetcode_id: 59
leetcode_url: https://leetcode.com/problems/spiral-matrix-ii/
categories:
  - arrays
patterns:
  - slug: matrix-traversal
    is_optimal: true

function_signature: "def generate_matrix(n: int) -> list[list[int]]:"

test_cases:
  visible:
    - input: { n: 3 }
      expected: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
    - input: { n: 1 }
      expected: [[1]]
  hidden:
    - input: { n: 2 }
      expected: [[1, 2], [4, 3]]
    - input: { n: 4 }
      expected: [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
    - input: { n: 5 }
      expected: [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]

description: |
  Given a positive integer `n`, generate an `n x n` matrix filled with elements from `1` to `n^2` in spiral order.

  The spiral order starts from the top-left corner and moves **right**, then **down**, then **left**, then **up**, repeating this pattern layer by layer until all cells are filled.

constraints: |
  - `1 <= n <= 20`

examples:
  - input: "n = 3"
    output: "[[1,2,3],[8,9,4],[7,6,5]]"
    explanation: "Starting from top-left, fill 1-3 going right, 4-5 going down, 6-7 going left, 8 going up, and 9 in the center."
  - input: "n = 1"
    output: "[[1]]"
    explanation: "A 1x1 matrix contains only the element 1."

explanation:
  intuition: |
    Imagine peeling an onion layer by layer, but in reverse — you're *building* layers from the outside in.

    Each "layer" of the spiral is like a rectangular frame around the matrix. For a 3x3 matrix, the outer layer contains positions for numbers 1-8, and the center (a 1x1 "layer") holds just the number 9.

    Think of it like walking around a track: you walk along the **top edge** from left to right, then down the **right edge**, then across the **bottom edge** from right to left, and finally up the **left edge**. After completing one lap, you step inward to the next track (layer) and repeat.

    The key insight is that you can define each layer by its **boundaries**: top row, bottom row, left column, and right column. After completing a layer, you shrink these boundaries inward and continue until no space remains.

  approach: |
    We solve this using a **Layer-by-Layer Simulation** approach:

    **Step 1: Initialise the matrix and boundaries**

    - Create an `n x n` matrix filled with zeros
    - `num`: Counter starting at `1`, incrementing as we fill each cell
    - `top`, `bottom`: Row boundaries, starting at `0` and `n-1`
    - `left`, `right`: Column boundaries, starting at `0` and `n-1`

    &nbsp;

    **Step 2: Fill the matrix layer by layer**

    While `top <= bottom` and `left <= right`, fill one complete layer:

    - **Fill top row**: Traverse from `left` to `right` along row `top`, then increment `top`
    - **Fill right column**: Traverse from `top` to `bottom` along column `right`, then decrement `right`
    - **Fill bottom row**: Traverse from `right` to `left` along row `bottom`, then decrement `bottom`
    - **Fill left column**: Traverse from `bottom` to `top` along column `left`, then increment `left`

    After each cell is filled, increment `num` to place the next number.

    &nbsp;

    **Step 3: Return the result**

    - Once the boundaries cross (`top > bottom` or `left > right`), all cells are filled
    - Return the completed matrix

    &nbsp;

    This simulation approach systematically handles each layer, shrinking the working area until the entire matrix is filled.

  common_pitfalls:
    - title: Off-by-One Errors in Boundaries
      description: |
        A frequent mistake is incorrectly updating or checking boundaries. For example, forgetting to increment `top` after filling the top row, or using `<` instead of `<=` in the while condition.

        With `n = 1`, `top == bottom == 0` and `left == right == 0`. If you use `top < bottom`, you'd skip the only cell entirely! Always use `<=` for the boundary checks.
      wrong_approach: "Using strict inequality (< instead of <=)"
      correct_approach: "Use <= to include single-row or single-column layers"

    - title: Forgetting to Adjust Boundaries After Each Edge
      description: |
        After traversing the top row, you must increment `top` before moving to the right column. Similarly for other edges. Forgetting this causes the same row or column to be overwritten.

        For example, without incrementing `top`, the right column traversal would start at the same row as the top row traversal ended, placing numbers in already-filled cells.
      wrong_approach: "Filling edges without updating boundaries"
      correct_approach: "Update the corresponding boundary immediately after each edge"

    - title: Not Handling Non-Square Subregions
      description: |
        While this problem uses square matrices, the layer technique must handle rectangular subregions that appear in later layers. For a 3x3 matrix, after the first layer, you have a 1x1 center — effectively a single cell.

        The condition `top <= bottom and left <= right` correctly handles this: when only one row or column remains, we fill just that portion without issues.
      wrong_approach: "Assuming all layers are full rectangles"
      correct_approach: "Let boundary conditions naturally handle degenerate cases"

  key_takeaways:
    - "**Boundary tracking**: Define layers by their four boundaries (`top`, `bottom`, `left`, `right`) and shrink inward after each complete layer"
    - "**Simulation pattern**: Some problems are best solved by directly simulating the described process rather than finding mathematical patterns"
    - "**Consistent direction order**: Always traverse in the same order (right → down → left → up) to maintain spiral consistency"
    - "**Foundation for related problems**: This technique directly applies to *Spiral Matrix* (reading values) and other matrix traversal problems"

  time_complexity: "O(n^2). We visit each of the `n^2` cells exactly once to place a number."
  space_complexity: "O(n^2). We create an `n x n` matrix to store the result. If we exclude the output, the algorithm uses O(1) auxiliary space."

solutions:
  - approach_name: Layer-by-Layer Simulation
    is_optimal: true
    code: |
      def generate_matrix(n: int) -> list[list[int]]:
          # Create n x n matrix filled with zeros
          matrix = [[0] * n for _ in range(n)]

          # Number to place, starting from 1
          num = 1

          # Define the boundaries of the current layer
          top, bottom = 0, n - 1
          left, right = 0, n - 1

          while top <= bottom and left <= right:
              # Fill top row: left to right
              for col in range(left, right + 1):
                  matrix[top][col] = num
                  num += 1
              top += 1  # Shrink top boundary

              # Fill right column: top to bottom
              for row in range(top, bottom + 1):
                  matrix[row][right] = num
                  num += 1
              right -= 1  # Shrink right boundary

              # Fill bottom row: right to left
              for col in range(right, left - 1, -1):
                  matrix[bottom][col] = num
                  num += 1
              bottom -= 1  # Shrink bottom boundary

              # Fill left column: bottom to top
              for row in range(bottom, top - 1, -1):
                  matrix[row][left] = num
                  num += 1
              left += 1  # Shrink left boundary

          return matrix
    explanation: |
      **Time Complexity:** O(n^2) — We place exactly `n^2` numbers, visiting each cell once.

      **Space Complexity:** O(n^2) — The output matrix requires `n^2` space. The algorithm itself uses O(1) auxiliary space (just boundary variables and the counter).

      We simulate the spiral by maintaining four boundaries. For each layer, we traverse all four edges in order, updating boundaries after each edge to "peel off" that layer and prepare for the next inner layer.

  - approach_name: Direction-Based Simulation
    is_optimal: false
    code: |
      def generate_matrix(n: int) -> list[list[int]]:
          # Create n x n matrix filled with zeros
          matrix = [[0] * n for _ in range(n)]

          # Direction vectors: right, down, left, up
          directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
          dir_idx = 0  # Start moving right

          row, col = 0, 0
          for num in range(1, n * n + 1):
              matrix[row][col] = num

              # Calculate next position
              next_row = row + directions[dir_idx][0]
              next_col = col + directions[dir_idx][1]

              # Check if we need to turn: out of bounds or cell already filled
              if (next_row < 0 or next_row >= n or
                  next_col < 0 or next_col >= n or
                  matrix[next_row][next_col] != 0):
                  # Turn clockwise: right -> down -> left -> up -> right
                  dir_idx = (dir_idx + 1) % 4
                  next_row = row + directions[dir_idx][0]
                  next_col = col + directions[dir_idx][1]

              row, col = next_row, next_col

          return matrix
    explanation: |
      **Time Complexity:** O(n^2) — We iterate through all `n^2` numbers.

      **Space Complexity:** O(n^2) — Same output matrix, plus O(1) for direction tracking.

      Instead of explicitly tracking layers, we move in the current direction until we hit a boundary or an already-filled cell, then turn clockwise. This is more intuitive for some but slightly less efficient due to boundary checks on every step.
