54. Spiral Matrix - Detailed Explanation

Problem Statement

Description:
You are given an m x n matrix containing integers. Your task is to return all the elements of the matrix in spiral order. The traversal starts at the top-left corner and proceeds in a spiral (clockwise) path until every element is visited.

Key Details:

• You must traverse the matrix in a spiral pattern (right → down → left → up, then repeat).
• The matrix can be rectangular (not necessarily a square).

Example Inputs, Outputs, and Explanations

1. Example 1:

   • Input:

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

   • Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
   • Explanation:
     • Start with the first row: 1, 2, 3
     • Then the last column (excluding the first element already visited): 6, 9
     • Then the last row in reverse: 8, 7
     • Then the first column upward: 4
     • Finally, the middle element: 5

2. Example 2:

   • Input:

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

   • Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
   • Explanation:
     • Traverse the top row: 1, 2, 3, 4
     • Then the right column: 8, 12
     • Then the bottom row in reverse: 11, 10, 9
     • Then the left column upward: 5
     • Finally, the remaining inner row: 6, 7

3. Example 3 (Edge Case):

   • Input: [] (an empty matrix)
   • Output: []
   • Explanation:
     • An empty matrix returns an empty list.

Constraints

• The matrix dimensions m (number of rows) and n (number of columns) can vary.
• It is possible that m != n, meaning the matrix can be rectangular.
• The matrix can be empty.

Hints to Approach the Solution

1. Boundary Variables:

   • Think of maintaining four boundaries: top, bottom, left, and right. These boundaries represent the current limits of the rows and columns that still need to be traversed.

2. Layer-by-Layer Traversal:

   • Process the matrix layer by layer (or ring by ring). For each layer, traverse:
     • From the left to the right on the top row.
     • From the top to the bottom on the right column.
     • From the right to the left on the bottom row (if the top and bottom rows are not the same).
     • From the bottom to the top on the left column (if the left and right columns are not the same).

3. Update Boundaries:

   • After processing one complete spiral layer, update the boundaries to move inward.

Approach 1: Simulation with Boundary Pointers

Explanation

• Idea:
  • Use four pointers (top, bottom, left, and right) to keep track of the boundaries.
  • While the pointers do not cross each other, traverse the outer layer in the order:
    1. Left to right (top row).
    2. Top to bottom (right column).
    3. Right to left (bottom row), if applicable.
    4. Bottom to top (left column), if applicable.
  • After each complete traversal, adjust the boundaries inward and repeat.

Pseudocode

result = []
top = 0, bottom = m - 1, left = 0, right = n - 1

while (top <= bottom and left <= right):
    # Traverse from left to right.
    for j from left to right:
        result.add(matrix[top][j])
    top += 1

    # Traverse from top to bottom.
    for i from top to bottom:
        result.add(matrix[i][right])
    right -= 1

    # Traverse from right to left if top <= bottom.
    if top <= bottom:
        for j from right to left:
            result.add(matrix[bottom][j])
        bottom -= 1

    # Traverse from bottom to top if left <= right.
    if left <= right:
        for i from bottom to top:
            result.add(matrix[i][left])
        left += 1

return result

Approach 2: Direction Array Simulation

Explanation

• Idea:
  • Use a direction vector (e.g., right, down, left, up) and a visited marker or boundaries to determine the next position.
  • This method simulates the movement until all elements are visited.
  • It is slightly more general, but for this problem the boundary approach is usually simpler.

Why the Boundary Approach is Often Preferred

• The boundary approach explicitly manages the layer-by-layer traversal and naturally handles the cases where the matrix is not a perfect square.
• It avoids extra space for visited flags since the boundaries implicitly track what has been visited.

Code Implementations

Python Code