Spiral Matrix

Problem Link

Spiral Matrix – LeetCode

Problem: Spiral Matrix

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Examples

Example 1
Input:
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output:
[1,2,3,6,9,8,7,4,5]

Example 2
Input:
matrix = [[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]

Constraints

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

Intuition

Spiral traversal follows this cyclic order:

1. Traverse top row left to right.

2. Traverse right column top to bottom.

3. Traverse bottom row right to left.

4. Traverse left column bottom to top.

Repeat this cycle while shrinking the bounds until all elements are visited.

Approach

1. Use four boundary pointers:

   • top, bottom, left, and right

2. Traverse in a spiral by:

   • Moving left → right on top row, then increment top

   • Moving top → bottom on right column, then decrement right

   • Moving right → left on bottom row (if still valid), then decrement bottom

   • Moving bottom → top on left column (if still valid), then increment left

3. Keep adding elements to the result list during traversal.

4. Stop when top > bottom or left > right.

Code (Java)

class Solution {
    public List<Integer> spiralOrder(int[][] mat) {
        int t = 0;                     // top row
        int l = 0;                     // left column
        int b = mat.length - 1;       // bottom row
        int r = mat[0].length - 1;    // right column

        List<Integer> ans = new ArrayList<>();

        while (t <= b && l <= r) {
            // Traverse top row
            for (int i = l; i <= r; i++) {
                ans.add(mat[t][i]);
            }
            t++;

            // Traverse right column
            for (int i = t; i <= b; i++) {
                ans.add(mat[i][r]);
            }
            r--;

            // Traverse bottom row (right to left)
            if (t <= b) {
                for (int i = r; i >= l; i--) {
                    ans.add(mat[b][i]);
                }
                b--;
            }

            // Traverse left column (bottom to top)
            if (l <= r) {
                for (int i = b; i >= t; i--) {
                    ans.add(mat[i][l]);
                }
                l++;
            }
        }

        return ans;
    }
}

Time and Space Complexity

• Time Complexity: O(m × n)
  Each element is visited exactly once.

• Space Complexity: O(1) (excluding the output list)

Dry Run

Input:

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

Initial:

• top = 0, bottom = 2

• left = 0, right = 2

1. Top row (left → right): 1, 2, 3
   → top = 1

2. Right col (top → bottom): 6, 9
   → right = 1

3. Bottom row (right → left): 8, 7
   → bottom = 1

4. Left col (bottom → top): 4
   → left = 1

Repeat:

5. Top row: 5
   → top = 2

6. Right col: no elements → skip

7. Bottom row: no elements → skip

8. Left col: no elements → skip

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

Conclusion

This problem demonstrates clean boundary-based traversal of a 2D array. By shrinking the boundaries after each direction of traversal, we ensure that all elements are visited in spiral order without overlap.