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

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
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
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

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.
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).
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

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- O(m * n) where m is the number of rows and n is the number of columns.
- Each element is visited exactly once.
Space Complexity:
- O(1) extra space (excluding the output list).
- The output list itself requires O(m * n) space to store the elements.

Step-by-Step Walkthrough (Visual Example)

Consider the matrix:

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

Initialization:
- top = 0, bottom = 2, left = 0, right = 2.
First Layer (Outer Ring):
- Traverse top row: Append [1, 2, 3] → update top to 1.
- Traverse right column: Append [6, 9] → update right to 1.
- Traverse bottom row: Append [8, 7] (reverse order) → update bottom to 1.
- Traverse left column: Append [4] (upwards) → update left to 1.
Second Layer (Inner Ring):
- Now only one element remains at matrix[1][1] which is 5.
- Append [5].
Final Result: [1, 2, 3, 6, 9, 8, 7, 4, 5].

Common Mistakes & Edge Cases

Common Mistakes

Boundary Overlap:
- Not checking whether the current top is still less than or equal to bottom or left is less than or equal to right before traversing a row or column.
Double Counting:
- Re-visiting elements if boundaries are not updated correctly.
Handling Single Row or Column:
- Special care is needed when the matrix has only one row or one column.

Edge Cases

Empty Matrix:
- Return an empty list.
Matrix with a Single Row or Column:
- The spiral order is the same as the row or column itself.
Non-Square Matrix:
- Ensure that the solution works for both rectangular and square matrices.

Variations

Spiral Matrix II:
- Instead of reading a matrix, generate a matrix filled with elements in spiral order.
Rotate Image:
- A related problem that involves rotating a matrix by 90 degrees.