Saturday, January 3, 2015

Spiral Matrix (LeetCode Array)

Question: Given a matrix of m x n elements (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].

Idea: Brute force. The left up corner and the bottom right corner of the i'th spiral is (0+i, 0+i) and (m-1-i, n-1-i), where i starts from 0.
The only special case is when there is only one row or only one column, the spiral will not goes back to the start point.

Time: O(m*n) Space: O(1)

Code:
 public class Solution {  
   public List<Integer> spiralOrder(int[][] matrix) {  
     List<Integer> result=new ArrayList<Integer>();  
     if(matrix.length==0||matrix[0].length==0)  
       return result;  
     int startI=0;  
     int startJ=0;  
     int endI=matrix.length-1;  
     int endJ=matrix[0].length-1;  
     while(startI<=endI&&startJ<=endJ)  
     {  
       if(startI==endI)  
       {  
         for(int j=startJ;j<=endJ;j++)  
           result.add(matrix[startI][j]);  
         break;  
       }  
       if(startJ==endJ)  
       {  
         for(int i=startI;i<=endI;i++)  
           result.add(matrix[i][startJ]);  
         break;  
       }  
       for(int j=startJ;j<=endJ;j++)  
         result.add(matrix[startI][j]);  
       for(int i=startI+1;i<=endI;i++)  
         result.add(matrix[i][endJ]);  
       for(int j=endJ-1;j>=startJ;j--)  
         result.add(matrix[endI][j]);  
       for(int i=endI-1;i>startI;i--)  
         result.add(matrix[i][startJ]);  
       startI++;  
       startJ++;  
       endI--;  
       endJ--;  
     }  
     return result;  
   }  
 }  

No comments:

Post a Comment