Concise JavaScript O(n) time and O(1) space using prefix and postfix products


  • 0
    var productExceptSelf = function(nums) {
        const res = [];
        let prev = 1;
        for (let k of nums) res.push(prev *= k);
        for (let prev = 1, i = nums.length - 1; i >= 0; prev *= nums[i--]) {
            res[i] = i ? prev * res[i - 1] : prev;
        }
        return res;
    };
    

    The insight for this problem is: the array product without an element is equal to that element's left-neighbor prefix product times its right-neighbor postfix product.

    The example problem [1, 2, 3, 4] has prefix products [1, 2, 6, 24] and postfix products [24, 24, 12, 4], so the answer at the element 3 is 2 × 4 = 8 and so on until we get the output array [24, 12, 8, 6]. A 1 product is implied beyond array bounds.


Log in to reply
 

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