Lintcode. Spiral Matrix

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

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].

 

Java
Time complexity: O(N*M), N – num of rows, M – num of columns
Space complexity: O(N*M), N – num of rows, M – num of columns

public class Solution {
    /**
     * @param matrix a matrix of m x n elements
     * @return an integer list
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        // Write your code here
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return new ArrayList<>();
        }
        
        int nRow = matrix.length;
        int nCol = matrix[0].length;
        
        List<Integer> res = new ArrayList<>();
        int lvlNum = Math.min(nRow, nCol) / 2 + (Math.min(nRow,nCol) % 2 > 0 ? 1 : 0);

        
        for (int level = 0; level < lvlNum; ++level){
            for (int col = level; col < nCol - level; ++col){
                res.add(matrix[level][col]);
            }
            for (int row = level + 1; row < nRow - level; ++row){
                res.add(matrix[row][nCol-level-1]);
            }
            if (nRow-level-1 == level){//avoid row overlap
                break;
            }
            for (int col = nCol - level - 2; col >= level; --col){
                res.add(matrix[nRow-level-1][col]);
            }
            if (level == nCol-level-1){//avoid column overlap
                break;    
            }
            for (int row = nRow-level-2; row > level; --row){
                res.add(matrix[row][level]);
            }
        }
        
        return res;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s