22) Product of Array Except Self

Thanks for this technique Claude:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length
    const results = Array(n).fill(1)
 
    let prefixProd = 1
    for (let i = 0; i < n; i++){
        results[i] *= prefixProd // use existing "prefix" to augment results
        // Each result is set to the prod of ALL previous numbers, but not itself
        // Although if these two lines were reversed, it would be inclusive of itself too
        prefixProd *= nums[i] // update "prefix" to include num
    }
 
    let suffixProd = 1
    for (let i = nums.length - 1; i >= 0; i--){
        results[i] *= suffixProd
        suffixProd *= nums[i]
    }
    
    return results
};

Memorized, understood, and time to completion down to 1:32

Not bad. This two pass system is very cool. It’s like weaving numbers.

Made a mistake at one point with:

prefixProd *= results[i]

But if it’s written this way, I believe the results at i will always be 1, and never be changed.

Return 1

Okay got it. Took a second to re-read, got it in about 2 minutes.

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length
    const results = Array(n).fill(1)
 
    let prefix = 1
    for (let i = 0; i < nums.length; i++){
        results[i] *= prefix
        prefix *= nums[i]
    }
 
    let suffix = 1
    for (let i = nums.length-1; i >= 0; i--){
        results[i] *= suffix
        suffix *= nums[i]
    }
 
    return results
};

Takes a second to wrap my head around it again. I wonder if this could be achieved with just one loop:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length
    const results = Array(n).fill(1)
 
    let prefix = 1
    let suffix = 1
    for (let i = 0; i < nums.length; i++){
        results[i] *= prefix
        prefix *= nums[i]
 
        const j = n - 1 - i
        console.log({i, j})
        results[j] *= suffix
        suffix *= nums[j]
 
    }
 
    return results
};

I dunno if this is better exactly. It’s a bit less straightforward to read in my opinion, but I do like it. It’s cool to console log out and see the index go in two directions at once, like Benjamin Button and a normal mortal, or two cars playing chicken.