Learning Journal

3/2/2024

Product of Array Except Self

function productExceptSelf(nums: number[]): number[] {
    const a = [1];

    for(let i = 1; i < nums.length; i++) {
        a.push(a[i - 1] * nums[i -1]);
    }

    const b = Array(nums.length).fill(1);

    for(let i = nums.length -2; i >= 0; i--){
        b[i] = b[i + 1] * nums[i+1];
    }

    for(let i = 0; i < nums.length; i++) {
        b[i] = b[i] * a[i];
    }

    return b;
};function productExceptSelf(nums: number[]): number[] {
    const a = [1];

    for(let i = 1; i < nums.length; i++) {
        a.push(a[i - 1] * nums[i -1]);
    }

    const b = Array(nums.length).fill(1);

    for(let i = nums.length -2; i >= 0; i--){
        b[i] = b[i + 1] * nums[i+1];
    }

    for(let i = 0; i < nums.length; i++) {
        b[i] = b[i] * a[i];
    }

    return b;
};

THE PROBLEM

The difficulty of this problem lies on its constraint which is the time complexity must not be greater than O(n). So, which mean we can only traverse the array several times, not n times. We can not go back to do anything while traversing.

So, when we go to the position i, we only know all of the elements from i to the beginning. Because we need to return the product, why don't we just store the product of all elements from start to i? We can do that.

But the problem is we don't know all the elements from i to end. So, we can go from the end, backward to 0 and store the product of all elements start from end and count backward to i. Then, all we do is multiply each pair of the elements in the two array.

There is another solution which is faster in Leetcode, which use a variable to keep track of the current product when we go backward. It turns out that we don't need to keep a whole array.

Revised by ChatGPT

The challenge in this problem is to achieve a time complexity of O(n), which means we can only traverse the array a constant number of times. We cannot afford to iterate through the array multiple times for each element.

To solve this, we can use a two-pass approach:

Forward Pass: Start from the beginning of the array and calculate the cumulative product of all elements up the the current index. Store these products in an array a. At each index i, a[i] will hold the product of all elements from the start up to i-1.
Backward Pass: Similarly, start from the end of the array and calculate the cumulative product of all elements from the end up to the current index. Store these products in another array b. At each index i, b[i] will hold the product of all elements from i+ 1 to the end.
Final Step: To get the final result, multiply the corresponding elements of arrays a and b. The product at each index i will be the product of all elements in the array except nums[i].

An optimization to this approach is to use a single array b and a variable to keep track of the cumulative product during the backward pass. This reduces the space complexity from O(n) to O(1), as we don't need to maintain a separate array for the forward pass.