59. Spiral Matrix II - Detailed Explanation

Problem Statement

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n² in spiral order. In other words, fill the matrix in a clockwise spiral pattern starting from the top-left corner.

For example, if n = 3, the output should be:

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

Example Inputs, Outputs, and Explanations

Example 1

• Input: n = 3
• Output:

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

• Explanation:
  • Start filling from the top row: 1, 2, 3.
  • Then fill the right column from top to bottom (excluding the already-filled top): 4.
  • Next, fill the bottom row from right to left: 5, 6, 7.
  • Finally, fill the left column from bottom to top: 8, and the center is 9.

Example 2

• Input: n = 1
• Output:

  [
   [1]
  ]
  

• Explanation:
  • With a single element, the spiral is just the element itself.

Hints

1. Four Pointers (Boundaries):
   Use four pointers to represent the current boundaries of the matrix:

   • top: starting row index
   • bottom: ending row index
   • left: starting column index
   • right: ending column index

2. Spiral Traversal:

   • Traverse the top row from left to right.
   • Traverse the right column from top to bottom.
   • Traverse the bottom row from right to left.
   • Traverse the left column from bottom to top.
   • After completing a full spiral, adjust the boundaries to move inward.

3. Loop Termination:
   Continue the process until the number to be inserted exceeds n².

Approach: Simulation Using Boundaries

Explanation

1. Initialize a Matrix:
   Create an n x n matrix filled with zeros (or any placeholder).

2. Set Up Boundaries and Start Value:

   • top = 0
   • bottom = n - 1
   • left = 0
   • right = n - 1
   • num = 1 (the starting number)

3. Fill the Matrix in a Spiral Order:

   • Traverse the top row: From index left to right. Then, increment top.
   • Traverse the right column: From index top to bottom. Then, decrement right.
   • Traverse the bottom row: From index right to left (if top ≤ bottom). Then, decrement bottom.
   • Traverse the left column: From index bottom to top (if left ≤ right). Then, increment left.
   • Continue until num > n².

4. Return the Result:
   The matrix is now filled in spiral order.

Step-by-Step Walkthrough

For n = 3:

• Initialize:
  • Matrix: a 3x3 grid of zeros.
  • Boundaries: top = 0, bottom = 2, left = 0, right = 2, num = 1.
• First Spiral:
  • Fill top row (row 0): positions (0,0) to (0,2) → [1, 2, 3]. Update top to 1.
  • Fill right column (column 2): rows 1 to 2 → [4, 5]. Update right to 1.
  • Fill bottom row (row 2): positions (2,1) to (2,0) → [6, 7]. Update bottom to 1.
  • Fill left column (column 0): row 1 → [8]. Update left to 1.
• Second Spiral (Center Element):
  • Now top = 1, bottom = 1, left = 1, right = 1. Fill (1,1) with 9.
• Final matrix:

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

Complexity Analysis

• Time Complexity: O(n²)
  Every element in the n x n matrix is visited exactly once.

• Space Complexity: O(n²)
  The space used to store the matrix is proportional to n².

Python Code