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