1352: Product-of-the-Last-K-Numbers
Medium

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:

From this example, we can deduce that:

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

learnings

time taken