54. Spiral Matrix

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

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]

Thoughts:

1. having four markers: rowBegin, rowEnd, colBegin, colEnd,

2. go right -> incre rowBegin; go down -> decre colEnd; go left -> check(rowBegin <= rowEnd), decre rowEnd; go up ->check(colBegin <= colEnd), incre colBegin

Code Java

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new LinkedList<Integer>();
        if(matrix.length == 0) return res;

        int rowBegin = 0, rowEnd = matrix.length - 1;
        int colBegin = 0, colEnd = matrix[0].length - 1;
        while(rowBegin <= rowEnd && colBegin <= colEnd){
                // go right
            for(int j = colBegin; j <= colEnd; j++){
                res.add(matrix[rowBegin][j]);
            }
            rowBegin++;

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

            // go left
            if(rowBegin <= rowEnd){
                for(int j = colEnd; j >= colBegin; j --){
                    res.add(matrix[rowEnd][j]);
                }    
            }
            rowEnd--;

            // go up
            if(colBegin <= colEnd){
                for(int i = rowEnd; i >= rowBegin; i--){
                    res.add(matrix[i][colBegin]);
                }
            }
            colBegin++;
        }

        return res;
    }
}

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        res = []
        if not matrix: return res

        rowS, colS, rowE, colE = 0, 0, len(matrix) - 1, len(matrix[0]) -1

        while rowS <= rowE and colS <= colE:
            # right
            for j in range(colS, colE + 1):
                res.append(matrix[rowS][j])
            rowS+= 1

            # down
            for i in range(rowS, rowE + 1):
                res.append(matrix[i][colE])
            colE-= 1

            # left
            if rowS <= rowE:
                for j in range(colE,colS - 1,-1):
                    res.append(matrix[rowE][j])
                rowE -= 1

            # up
            if colS <= colE:
                for i in range(rowE, rowS - 1, -1):
                    res.append(matrix[i][colS])
                colS+= 1

        return res

from qwl5004's post