Friday, 18 December 2015

LeetCode Spiral Matrix O(n) time complexity and O(1) extra space

LeetCode Spiral Matrix O(n) time complexity and O(1) extra space

class Solution {

public:

    vector<int> spiralOrder(vector<vector<int> >& matrix) {

      vector < int > ans;

      int row=matrix.size();

      if(row==0)

       return ans;

      int column=matrix[0].size();

      if(column==0)

       return ans;

      int s1,s2,n=row*column;

      int e1=row,e2=column;

      int i=0,j=0,cnt=0;

     while(cnt<n){

      s1=i;s2=j;

      while(s2<e2){

            ans.push_back(matrix[s1][s2]);

          s2++;cnt++;

      }

      if(cnt==n)

           break;

      s1=i+1;s2=e2-1;

      while(s1<e1){

           ans.push_back(matrix[s1][s2]);

           s1++;cnt++;

      }

      if(cnt==n)

           break;

      s1=e1-1;s2=e2-2;

      while(s2>=j){

          ans.push_back(matrix[s1][s2]);

          s2--;cnt++;

      }

      if(cnt==n)

           break;

      s1=e1-2;s2=j;

      while(s1>i){

          ans.push_back(matrix[s1][s2]);

          s1--;cnt++;

      }

      if(cnt==n)

           break;

      i=i+1;j=j+1;

      e1=e1-1;e2=e2-1;

     }

     return ans;

    }

};

No comments:

Post a Comment