Given an m x n matrix, return all elements in spiral order (clockwise from top-left).
Input: [[1,2,3],[4,5,6],[7,8,9]] → Output: [1,2,3,6,9,8,7,4,5]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]
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.
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