Skip to content
AI360Xpert
Back to Math & Geometry
Medium

Spiral Matrix

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

Examples

Input:matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output:[1,2,3,6,9,8,7,4,5]
Follow the spiral from the outside in.
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]
Follow the spiral from the outside in.

Constraints

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

Four Boundaries

Approach

We define four boundaries: `top`, `bottom`, `left`, and `right`. We iterate through the matrix by moving in a spiral: left to right (top row), top to bottom (right column), right to left (bottom row), and bottom to top (left column). After completing each traversal, we update the corresponding boundary (e.g., after the top row is done, `top++`). We repeat this process until the boundaries cross each other (`left <= right` and `top <= bottom`). Note: Before traversing right to left or bottom to top, we must verify that `top <= bottom` and `left <= right` respectively, because the matrix might not be square.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(1)

Time complexity is O(m * n) since we visit each element exactly once. Space complexity is O(1) if we don't count the output array.

Solution.java
class Solution {    public List<Integer> spiralOrder(int[][] matrix) {        List<Integer> res = new ArrayList<>();        if (matrix == null || matrix.length == 0) return res;                int top = 0;        int bottom = matrix.length - 1;        int left = 0;        int right = matrix[0].length - 1;                while (top <= bottom && left <= right) {            // Traverse Top            for (int i = left; i <= right; i++) {                res.add(matrix[top][i]);            }            top++;                        // Traverse Right            for (int i = top; i <= bottom; i++) {                res.add(matrix[i][right]);            }            right--;                        // Traverse Bottom (check condition)            if (top <= bottom) {                for (int i = right; i >= left; i--) {                    res.add(matrix[bottom][i]);                }                bottom--;            }                        // Traverse Left (check condition)            if (left <= right) {                for (int i = bottom; i >= top; i--) {                    res.add(matrix[i][left]);                }                left++;            }        }                return res;    }}