Discussion on: Daily Coding Problem #2

[Tiago Romero Garcia]

Javascript solution, no division, O(n) time.

The idea is basically two steps:

1. Walk over the list, and for each item, create an object which has the subproduct of itself and all the previous items, and also the item. That takes O(n).
2. With that list in hand, walk it backwards, for each object multiplying the subproduct of the previous items with the subproduct of the remaining items. That also takes O(n).

I also do a 3rd step to map from that object to the subproducts, but that could be spared if we created a new array during step 1, but still that step would still keep it O(n)

function productOfAllButI(list) {
    const n = list.length;
    const itemsButI = [{product: 1, item: list[0]}];

    for (let i = 1; i < n; i++) {
        const previous = itemsButI[i - 1];
        const item = list[i];
        const product = previous.product * previous.item;
        itemsButI.push({ product, item });
    }

    let remainingSubProduct = 1;
    for (let i = n-1; i >= 0; i--) {        
        const current = itemsButI[i];
        current.product *= remainingSubProduct;
        remainingSubProduct *= current.item;
    }

    return itemsButI.map(({product}) => product);
}