medium Spiral Matrix

Problem Statement

Given a 2D matrix of size m x n, return the 1D array containing all elements of matrix in spiral order.

Examples

Example 1:

• Input: matrix =

[[1,2,3,4],
 [5,6,7,8], 
 [9,10,11,12],
 [13,14,15,16]]

• Expected Output: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
• Justification: We have traversed the matrix in the spiral order.

Example 2:

• Input: matrix =

[[10,20,30],
 [40,50,60],
 [70,80,90]]

• Expected Output: [10,20,30,60,90,80,70,40,50]
• Justification: The traversal starts at the top-left, moves right to the end of the row, then down the right column, then left along the bottom row, up the left column, and finally captures the center.

Example 3:

• Input: matrix =

[[1,2],
 [3,4],
 [5,6]]

• Expected Output: [1,2,4,6,5,3]
• Justification: The traversal starts at the top-left, moves right, then down through the right column, and finally moves up the left column.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

Pattern / bounds discipline

Layer peel with four bounds. Recognition: visit every cell once in clockwise (or CCW) ring order. Maintain top, bottom, left, right. Each layer: right across top → down right column → left across bottom (only if top ≤ bottom) → up left column (only if left ≤ right). After each leg, shrink that bound by 1.

Why the guards matter: for a single remaining row, the top pass consumes it and top++ makes top > bottom; without the bottom-pass guard you would re-traverse that row leftward and duplicate cells. For a single remaining column, the right pass consumes it; without the left-pass guard you would walk it twice. These are the classic spiral off-by-one traps on non-square matrices (e.g. 1×n, m×1, 3×2).

Complexity: each of m·n cells is written once → O(m·n) time; O(1) extra besides the output list.

Solution

Peel the matrix layer by layer using four boundary pointers. In each iteration traverse the current ring in order (top row L→R, right col T→B, bottom row R→L, left col B→T), shrinking the active rectangle after each side. The top ≤ bottom / left ≤ right checks prevent double-counting when only one row or column remains.

Step-by-step Algorithm

• Initialize four pointers: top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1.
• Create an empty list result to store the spiral order.
• While (top <= bottom && left <= right):
  • Traverse from left to right at the top row. After traversing, increment top pointer.
  • Traverse from top to bottom at the right column. After traversing, decrement right pointer.
  • If (top <= bottom), traverse from right to left at the bottom row. After traversing, decrement bottom pointer.
  • If (left <= right), traverse from bottom to top at the left column. After traversing, increment left pointer.
• Return the result list containing the elements in spiral order.

Algorithm Walkthrough

1. Initialize Boundary Pointers and Result Container:

   • Top = 0 (index of the first row)
   • Bottom = 3 (index of the last row)
   • Left = 0 (index of the first column)
   • Right = 3 (index of the last column)
   • Result = [] (an empty list to store the spiral order)

2. First Outer Layer Traversal:

   • Traverse from Left to Right along the Top row:
     • Add elements 1, 2, 3, and 4 to Result.
   • Increment Top to 1 (moving the top boundary down to exclude the traversed row).
   • Traverse from Top to Bottom along the Right column:
     • Add elements 8, 12, and 16 to Result.
   • Decrement Right to 2 (moving the right boundary left to exclude the traversed column).
   • Since Top ≤ Bottom, traverse from Right to Left along the Bottom row:
     • Add elements 15, 14, and 13 to Result.
   • Decrement Bottom to 2 (moving the bottom boundary up to exclude the traversed row).
   • Since Left ≤ Right, traverse from Bottom to Top along the Left column:
     • Add elements 9 and 5 to Result.
   • Increment Left to 1 (moving the left boundary right to exclude the traversed column).

3. Second Inner Layer Traversal:

   • Now, the pointers are adjusted to: Top = 1, Bottom = 2, Left = 1, Right = 2.
   • Traverse from Left to Right along the new Top row (which is the second row now):
     • Add elements 6 and 7 to Result.
   • Increment Top to 2.
   • Traverse from Top to Bottom along the Right column:
     • Add element 11 in the results.
   • Decrement Right to 1 (moving the right boundary left to exclude the traversed column).
   • Since Top ≤ Bottom, traverse from Right to Left along the Bottom row:
     • Add element 10 to Result.
   • Decrement Bottom to 1 (moving the bottom boundary up to exclude the traversed row).
   • Stop traversal as top > bottom, and left > right.

4. Final Result Compilation:

   • After completing the spiral traversal correctly, the Result list now contains:

     [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
     

   • This sequence correctly represents the spiral order traversal of the given matrix.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {

  public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    // Validate input
    if (matrix == null || matrix.length == 0) return result;

    // Initialize boundary pointers
    int top = 0, bottom = matrix.length - 1, left = 0, right =
      matrix[0].length - 1;

    // Traverse the matrix in a spiral order
    while (top <= bottom && left <= right) {
      // Traverse from left to right
      for (int i = left; i <= right; i++) result.add(matrix[top][i]);
      top++;

      // Traverse from top to bottom
      for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
      right--;

      // Traverse from right to left if top <= bottom
      if (top <= bottom) {
        for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
        bottom--;
      }

      // Traverse from bottom to top if left <= right
      if (left <= right) {
        for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
        left++;
      }
    }

    return result;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    int[][] matrix1 = { { 10, 20, 30 }, { 40, 50, 60 }, { 70, 80, 90 } };
    System.out.println(sol.spiralOrder(matrix1));

    // Example 2
    int[][] matrix2 = { { 1, 2 }, { 3, 4 }, { 5, 6 } };
    System.out.println(sol.spiralOrder(matrix2));

    // Example 3 (Revised)
    int[][] matrix3 = {
      { 1, 2, 3, 4 },
      { 5, 6, 7, 8 },
      { 9, 10, 11, 12 },
      { 13, 14, 15, 16 },
    };
    System.out.println(sol.spiralOrder(matrix3));
  }
}

Complexity Analysis

Time Complexity

• , where m * n is the total number of elements in the matrix. Each element is visited exactly once, making the time complexity linear in terms of the number of elements in the matrix.

Space Complexity

• , disregarding the output array. The algorithm uses a constant amount of space for the pointers (top, bottom, left, right) and the result list's space is not considered part of the algorithm's space complexity as it is required for the output.
• If we consider the output space, then the space complexity is , where m * n is the total number of elements in the matrix.

🎯 STRICT STANDOUT: Why / complexity derivation / pattern+when-not / edges / drills — Solution Spiral Matrix

Why this exists (judgment layer)

Layer peel with four bounds is the transferable spiral/ring traversal pattern. Guards top≤bottom / left≤right prevent the single-row/column double-count bug on non-square mats.

Worked example & complexity derivation

3×2: [[1,2],[3,4],[5,6]]
top0 bot2 left0 right1
→ right on top: 1,2; top=1
→ down right col: 4,6; right=0
→ bottom right→left if top≤bot: 5; bot=1
→ up left if left≤right: 3; left=1
done → [1,2,4,6,5,3]
Without bottom guard on 1×n: after top pass top>bot, bottom pass would reverse-duplicate
Time Θ(m·n) each cell once; extra space O(1) + output

Pattern transfer & when-NOT

Pattern: LAYER PEEL four-bounds spiral. When-NOT: generate spiral matrix from 1..n² → same bounds write not read; diagonal-only → index arithmetic; random free roam → DFS/BFS. Direction-array simulation also works; bounds peel is clearer for rings.

Edge cases (hand-run)

1×n row only; m×1 col only; 1×1 single. Odd layers leave a center single cell — still handled if guards correct. m,n ≤10 in constraints but algorithm is general.

Hostile-panel drills (defend the decision)

Q1. Why if (top≤bottom) before bottom pass?
Model answer: Top pass may have consumed the last row; without guard you traverse it again leftward.

Q2. Complexity vs visiting with a seen[][] matrix?
Model answer: Both Θ(m·n) time; seen uses Θ(m·n) space; bounds peel is O(1) extra.

Q3. Output for [[10,20,30],[40,50,60],[70,80,90]]?
Model answer: [10,20,30,60,90,80,70,40,50].