54 Spiral Matrix

54. Spiral Matrix

1. Question

Given a matrix ofmxnelements (m rows,n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

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

You should return[1,2,3,6,9,8,7,4,5].

2. Implementation

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();

        if (matrix == null || matrix.length == 0) {
            return res;
        }

        int m = matrix.length, n = matrix[0].length;
        int rowStart = 0, rowEnd = m - 1, colStart = 0, colEnd = n - 1;

        while (rowStart <= rowEnd && colStart <= colEnd) {
            for (int j = colStart; j <= colEnd; j++) {
                res.add(matrix[rowStart][j]);
            }
            ++rowStart;

            for (int i = rowStart; i <= rowEnd; i++) {
                res.add(matrix[i][colEnd]);
            }
            --colEnd;

            // Edge Case: 当矩阵行数不等于列数时
            if (rowStart > rowEnd || colStart > colEnd) {
                break;
            }

            for (int j = colEnd; j >= colStart; j--) {
                res.add(matrix[rowEnd][j]);
            }
            --rowEnd;

            for (int i = rowEnd; i >= rowStart; i--) {
                res.add(matrix[i][colStart]);
            }
            ++colStart;
        }
        return res;
    }
}

3. Time & Space Complexity

时间复杂度O(m + n), 空间复杂度O(mn)