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]
[code lang="java"]
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
    }
}
[code]

Idea – 1

Spiral pattern goes layer by layer – from outer layer towards inner layer.
We go n places rightwards, we go m-1 one places downwards, we go n-1 places leftwards, and m-2 places upwards – that ends one layer. We keep processing layers in this way until either n or m for a layer becomes zero, which means no more layers to process. Time complexity O(m\cdot n). Excluding output, space complexity O(1). 
[code lang="java"]
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if(matrix == null)
        {
            return ans;
        }
        
        int m = matrix.length;
        if(m == 0)
        {
            return ans;
        }
        
        int n = matrix[0].length;
        
        // we are entering the matrix from left
        int i = 0, j = -1;
        while(n > 0)
        {
            // go n places rightwards
            for(int k = 0; k < n; ++k)
            {
                ans.add(matrix[i][++j]);
            }
            
            --m;
            if(m == 0)
            {
                break;
            }
            
            // go m-1 places downwards
            for(int k = 0; k < m; ++k)
            {
                ans.add(matrix[++i][j]);
            }
            
            --n;
            if(n == 0)
            {
                break;
            }
            
            // go n-1 places leftwards
            for(int k = 0; k < n; ++k)
            {
                ans.add(matrix[i][--j]);
            }
            
            --m;
            if(m == 0)
            {
                break;
            }
            
            // go m-2 places upwards
            for(int k = 0; k < m; ++k)
            {
                ans.add(matrix[--i][j]);
            }
            
            // prepare n for next layer
            --n;
        }
        
        return ans;
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Spiral Matrix.Memory Usage: 33.5 MB, less than 100.00% of Java online submissions for Spiral Matrix.

Leave a comment