My C++ code with forward-backward scans (O(N) time, O(1) space except output array)


  • 0
    D

    The basic idea is to do two scans to calculate the left part product nums[0]..nums[i-1] and the right part product nums[i+1]..nums[N-1], and the product of the two output products is the final result for element i.
    first do forward scan to calculate product of nums[0]..nums[i-1], which is the product of the left part of element i, and save it to res[i]
    then do backward scan to calculate product of nums[N-1]..nums[i+1], which is saved to rightProd,
    then calculate rightProd * res[i] to get the final result

     class Solution {
            public:
                vector<int> productExceptSelf(vector<int>& nums) {
                    vector<int> res(nums.size(),1);
                    int i, rightProd =1;
                    for(i=1;i<nums.size();++i) res[i] = res[i-1]*nums[i-1];                  //first foward scan 
                    for(i=nums.size()-2; i>=0; --i) res[i] *= (rightProd *= nums[i+1]); //then backward scan and update the result
                    return res;
                    
                }
        };

Log in to reply
 

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