A Simple C++ Solution with O(n) time and O(1) space


  • 0
    S
    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            if (matrix.empty()){
                vector<int> a;
                return a;
            }
            int t = 0, l = 0, r = matrix[0].size() - 1, d = matrix.size() - 1;
            int count = (r+1) * (d+1);
            vector<int> ans;
            ans.reserve(count);
            int i=0, j=0;
            
            while(count > 0){
                while(j <= r){
                    ans.push_back(matrix[i][j]);
                    count--;        
                    j++;
                }
                if (count <= 0){
                    break;
                }
                r--;
                j--;
                i++;
                while(i <= d){
                    ans.push_back(matrix[i][j]);
                    count--;        
                    i++;
                }
                if (count <= 0){
                    break;
                }
                d--;
                i--;
                j--;
                while(j >= l){
                    ans.push_back(matrix[i][j]);
                    count--;        
                    j--;
                }
                if (count <= 0){
                    break;
                }
                l++;
                j++;
                i--;
                while(i > t){
                    ans.push_back(matrix[i][j]);
                    count--;        
                    i--;
                }
                t++;
                i++;
                j++;
            }
            
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.