Problem statement

Numbers arrive one at a time. At any moment you may be asked for the product of the most recent k of them.

Write the class ProductOfNumbers:

• ProductOfNumbers() starts with an empty stream.
• void add(int num) appends num to the stream.
• int getProduct(int k) returns the product of the last k numbers in the stream. At least k numbers have been added whenever it is called.

The stream is guaranteed to stay small enough that the product of any contiguous run of its numbers fits in a signed 32-bit integer.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["ProductOfNumbers","add","add","add","getProduct","getProduct","add","getProduct","add","getProduct"]
[[],[3],[2],[5],[2],[3],[0],[2],[4],[1]]
Output: [null,null,null,null,10,30,null,0,null,4]
Explanation: After 3, 2, 5 the last two multiply to 10 and the last three to 30. Once a 0 arrives, any product that reaches back over it is 0. After 4 is added, the last one number is 4.

Example 2

Input: ["ProductOfNumbers","add","add","getProduct","getProduct"]
[[],[100],[7],[1],[2]]
Output: [null,null,null,7,700]
Explanation: The last number is 7; the last two are 100 and 7.

Constraints

• 0 <= num <= 100
• 1 <= k <= 4 * 10^4
• At most 4 * 10^4 calls are made to add and getProduct
• k never exceeds the number of numbers added so far
• The product of any contiguous run of the stream fits in a signed 32-bit integer

Follow-up: Can you make every call O(1)?

Hints for Product of the Last K Numbers

1. Hint 1

   For sums of the last k numbers you would keep prefix sums and subtract. Products have the same trick with division: last-k product = prefix[n] / prefix[n - k].

2. Hint 2

   Division breaks on zeros: a prefix product that has passed a 0 is 0 forever after.

3. Hint 3

   When a 0 arrives, throw the prefix list away and start again from [1]. Then if k reaches back further than the list does, the window contains that 0 and the answer is 0; otherwise divide.

How to solve Product of the Last K Numbers

Keep prefix products of the numbers since the last zero. Any window that stays inside that stretch is a quotient of two prefixes; any longer window contains a zero.

Approach

1. Start with pre = [1].
2. add(num): if num == 0, reset pre = [1]; otherwise append pre[last] * num.
3. getProduct(k): if k >= pre.length, the last k numbers include the most recent zero — return 0.
4. Otherwise return pre[last] / pre[last - k].

Why it works

After the reset, pre[i] is the product of the first i numbers added since the last zero, so the product of the last k of them is pre[m] / pre[m - k] — exact, because every factor is a positive integer that divides out. pre has one more entry than there are numbers since the zero, so k >= pre.length means the window reaches the zero itself. Each pre[i] is a contiguous product, so it fits in 32 bits by the guarantee.

Complexity

• Time — O(1) per call (amortised for the list append)
• Space — O(n)

Pitfalls

• Without the reset a single 0 makes every later prefix 0 and the division undefined.
• Multiplying the last k numbers on every query is O(k) — 1.6 × 10^9 steps at the limits.
• The comparison is k >= len(pre), not >: pre starts with the extra 1.

Reference solution

Python

class ProductOfNumbers:

    def __init__(self):
        self.pre = [1]  # prefix products since the last zero

    def add(self, num: int) -> None:
        if num == 0:
            self.pre = [1]
        else:
            self.pre.append(self.pre[-1] * num)

    def getProduct(self, k: int) -> int:
        if k >= len(self.pre):
            return 0  # the window reaches back to a zero
        return self.pre[-1] // self.pre[-1 - k]

Java

class ProductOfNumbers {
    private List<Integer> pre = new ArrayList<>(); // prefix products since the last zero

    public ProductOfNumbers() {
        pre.add(1);
    }

    public void add(int num) {
        if (num == 0) { pre.clear(); pre.add(1); }
        else pre.add(pre.get(pre.size() - 1) * num);
    }

    public int getProduct(int k) {
        int n = pre.size();
        if (k >= n) return 0; // the window reaches back to a zero
        return pre.get(n - 1) / pre.get(n - 1 - k);
    }
}

C++

class ProductOfNumbers {
    vector<int> pre{1}; // prefix products since the last zero
public:
    ProductOfNumbers() {}

    void add(int num) {
        if (num == 0) pre.assign(1, 1);
        else pre.push_back(pre.back() * num);
    }

    int getProduct(int k) {
        int n = pre.size();
        if (k >= n) return 0; // the window reaches back to a zero
        return pre[n - 1] / pre[n - 1 - k];
    }
};

JavaScript

var ProductOfNumbers = function() {
    this.pre = [1]; // prefix products since the last zero
};

ProductOfNumbers.prototype.add = function(num) {
    if (num === 0) this.pre = [1];
    else this.pre.push(this.pre[this.pre.length - 1] * num);
};

ProductOfNumbers.prototype.getProduct = function(k) {
    var n = this.pre.length;
    if (k >= n) return 0; // the window reaches back to a zero
    return this.pre[n - 1] / this.pre[n - 1 - k];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium