Easy-to-understand O(n) C++ solution, constant space


  • 2
    C
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        long l = 1, r = 1;
        
        for (int i = 1; i < n; i++) {
            l *= nums[i-1];  // process the bot-left triangle
            res[i] *= l;
        }
        
        for (int i = 1; i < n; i++) {
            r *= nums[n-i];  // process the upper-right triangle
            res[n-i-1] *= r;
        }
        
        return res;
    }

Log in to reply
 

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