Javascript O(n) solution


  • 0
    P

    The solution at any index i is equal to the cumulative product calculated by traversing LTR at [i-1] multiplied by the cumulative product calculated by traversing RTL at [i + 1] .

    Time complexity: O(n)
    Space complexity: Always uses 2 arrays but I don't think this qualifies as constant space because the sizes of these arrays grows with n.

    Solution:

    const productExceptSelf = function(nums) {    
        const forward = nums.reduce((a, v, i) => (
           a[i] = v * (i - 1 > -1 ? a[i-1] : 1), a
        ), []);
    
        const reverse = nums.reduceRight((a, v, i) => ( 
            a[i] = v * (i + 1 < nums.length ? a[i+1] : 1), a
        ), []); 
        
        return nums.map((v, i) => 
            (i - 1 > -1 ? forward[i-1] : 1) * 
            (i + 1 < nums.length ? reverse[i+1] : 1)
        );
    };
    

Log in to reply
 

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