Product of the Last K Numbers

It is quite straight-forward to come-up with the O(n) solution for this question; on every add operation, just multiple every existing value in the vector by num so that our getProduct operation is O(1).

My intuition told me that the constant time solution depended on a prefix product array, products. An example we can look over would be 3 0 2 5 4 8. First, let us define that the value at index position i is just getProduct(getProducts.size()-i), e.g. on row 6, 32 is getProduct(6-4) = getProduct(2) as the product of the last 2 numbers is 8 * 4 = 32.

Then, at each step, we can list out all the possible getProduct return values:

1. 3
2. 0, 0
3. 0, 0, 2
4. 0, 0, 10, 5
5. 0, 0, 40, 20, 4
6. 0, 0, 320, 160, 32, 8

From this example, we can deduce that:

• products has to be cleared and reinitialized every time we iterate over a 0.
  • This is because it would make consequent values in products equal to 0 as well, meaning there is no reason to store these value before as they will all be equal to 0.
• whenever we initialize products, it has to be created with products.size() == 1 and products[0] = 1. Then,
  • for k < products.size(), we have to return products.back() / products[products.size() - k - 1]. We can easily see this with an example, take row 6: 0 0 320 160 32 8, where the products array should equal 1, 2, 10, 40, 320, then e.g. getProduct(3) = 320 / 2 = 160
  • for k >= products.size(), it implies that we have previously encountered a 0 and had to clear the products array, meaning we should return 0.

code

class ProductOfNumbers {
public:
    ProductOfNumbers() {

    }

    void add(int num) {
        if (num == 0) {
            products.clear();
            products.push_back(1);
        } else {
            products.push_back(products[products.size()-1]*num);
        }
    }

    int getProduct(int k) {
        if (products.size() <= k) {
            return 0;
        } else {
            return products[products.size()-1] / products[products.size()-k-1];
        }
    }
private:
    vector<int> products = {1};
};

complexity

• Time: O(1)
• Space: O(n)

learnings

• for all array manipulation questions, if it talks about grouping a contiguous subset of elements, think about prefix arrays

time taken

• 27:37.08 seconds on Google Stopwatch
• spent most time trying to:
  • find the O(1) solution (prefix arrays)