Saturday, January 3, 2015

Spiral Matrix II (LeetCode Array)

Question: Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Idea: First initialize the n*n matrix. Then fill each of the spirals with a self-increasing counter (counter++). The top left corner of the i'th spiral is (0+i, 0+i), the bottom right corner of the i'th spiral is (n-1-i, n-1-i), where i starts from 0. There is a special case that the last spiral may be just one row or one column that the pointer should not come back.

Time: O(n^2) Space: O(1)

Code:
 public class Solution {  
   public int[][] generateMatrix(int n) {  
     int[][] matrix=new int[n][n];  
     int counter=1;  
     int startI=0;  
     int startJ=0;  
     int endI=n-1;  
     int endJ=n-1;  
     while(startI<=endI&&startJ<=endJ)  
     {  
       if(startI==endI)  
       {  
         for(int j=startJ;j<=endJ;j++)  
           matrix[startI][j]=counter++;  
         break;  
       }  
       if(startJ==endJ)  
       {  
         for(int i=startI;i<=endI;i++)  
           matrix[i][startJ]=counter++;  
         break;  
       }  
       for(int j=startJ;j<endJ;j++)  
         matrix[startI][j]=counter++;  
       for(int i=startI;i<endI;i++)  
         matrix[i][endJ]=counter++;  
       for(int j=endJ;j>startJ;j--)  
         matrix[endI][j]=counter++;  
       for(int i=endI;i>startI;i--)  
         matrix[i][startJ]=counter++;  
       startI++;  
       startJ++;  
       endI--;  
       endJ--;  
     }  
     return matrix;  
   }  
 }  

No comments:

Post a Comment