Problem Statement


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]

Solution Explanation

This problem seems little tricky but it is very easy to understand once you understand how spiral order works, and this question is often asked on onsite interviews.

So, first of all, let's think about how spiral order works. Spiral order follow four directions: It goes to the right, down, left and up in the order respectively.

To solve this problem, we are just going to follow these four directions order in our matrix and solve it. Read the comments provided in below solution code to understand further more.


class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
        //List initialization
        List<Integer> list = new ArrayList<>();
        
        if(matrix.length == 0 || matrix[0].length == 0) return list;
        
        //Initialized rowBegin,rowEnd,colBegin and ColEnd
        int rowBegin = 0; 
        int rowEnd = matrix.length -1;
        int colBegin = 0;
        int colEnd = matrix[0].length -1;
        
        
        while(rowBegin <= rowEnd && colBegin <= colEnd){
            
            //Traverse right and increment rowBegin
            for(int i = colBegin; i <= colEnd; i++){
                list.add(matrix[rowBegin][i]);
            }
            rowBegin++;
            
            //Traverse down and decrement colEnd
            for(int i = rowBegin; i <= rowEnd; i++){
                list.add(matrix[i][colEnd]);
            }
            colEnd--;
            
            //The only tricky part here is when we traverse left or up, we have to make sure whether that row or column still exists to prevent duplicates
            
            //Make sure that row exists 
            //And traverse left and decrement rowEnd
            if(rowBegin <= rowEnd){
                for(int i = colEnd; i >= colBegin; i--){
                    list.add(matrix[rowEnd][i]);
                }
            }
            rowEnd--;
            
            //Make sure that column exists
            //And traverse up and increment colBegin
            if(colBegin <= colEnd){
                for(int i = rowEnd; i >= rowBegin; i--){
                    list.add(matrix[i][colBegin]);
                }
            }
            colBegin++;
        }
        return list;
    }
}

Time Complexity

We are visiting each elements in given matrix so time complexity is going to be: O(m*n).

Space Complexity

We are adding each elements we visit in matrix to list, so space complexity is going to be: O(m*n).