Spiral Matrix

Share

Given an m x n matrix, return all elements in spiral order (clockwise from top-left).

Example 1
Input: [[1,2,3],[4,5,6],[7,8,9]] → Output: [1,2,3,6,9,8,7,4,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]

Solution Approach

Use four boundary pointers (top, bottom, left, right). Traverse right, down, left, up, shrinking boundaries after each pass.

  • top=0, bottom=m-1, left=0, right=n-1.
  • While top<=bottom and left<=right: traverse right row, down col, left row (if still valid), up col (if still valid).
  • Shrink boundaries after each direction.
Java
import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int top=0, bottom=matrix.length-1, left=0, right=matrix[0].length-1;
        while (top<=bottom && left<=right) {
            for (int c=left;c<=right;c++) res.add(matrix[top][c]); top++;
            for (int r=top;r<=bottom;r++) res.add(matrix[r][right]); right--;
            if (top<=bottom) { for (int c=right;c>=left;c--) res.add(matrix[bottom][c]); bottom--; }
            if (left<=right) { for (int r=bottom;r>=top;r--) res.add(matrix[r][left]); left++; }
        }
        return res;
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(1) extra