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


  • 0
    S
    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            int t = 0, l = 0, r = n - 1, d = n - 1;
            int count = n * n;
            int num = 1;
            vector<vector<int>> ans;
            ans.reserve(count);
            for(int i=0; i<n; i++){
                vector<int> list;
                list.reserve(n);
                for(int j=0; j<n; j++){
                    list.push_back(0);
                }
                ans.push_back(list);
            }
            
            int i=0, j=0;
            
            while(count > 0){
                while(j <= r){
                    ans[i][j] = num;
                    num++;
                    count--;        
                    j++;
                }
                if (count <= 0){
                    break;
                }
                r--;
                j--;
                i++;
                while(i <= d){
                    ans[i][j] = num;
                    num++;
                    count--;        
                    i++;
                }
                if (count <= 0){
                    break;
                }
                d--;
                i--;
                j--;
                while(j >= l){
                    ans[i][j] = num;
                    num++;
                    count--;        
                    j--;
                }
                if (count <= 0){
                    break;
                }
                l++;
                j++;
                i--;
                while(i > t){
                    ans[i][j] = num;
                    num++;
                    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.