1352. Product of the Last K Numbers

LeetCode 力扣

1. Description

Maintain a stream of integers and support queries for the product of its last k elements.
Implement the ProductOfNumbers class:

  • ProductOfNumbers() Creates an empty stream.
  • void add(int num) Appends num to the stream.
  • int getProduct(int k) Returns the product of the last k elements. The stream always contains at least k elements when queried.

Every contiguous sequence has a product that fits in a signed 32-bit integer.
Follow-up: Can both add and getProduct run in O(1) time?

2. Example

Example 1

Input
[“ProductOfNumbers”,“add”,“add”,“add”,“add”,“add”,“getProduct”,“getProduct”,“getProduct”,“add”,“getProduct”]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
Output
[null,null,null,null,null,null,20,40,0,null,32]
Explanation: After adding [3,0,2,5,4], the last two numbers multiply to 20, the last three to 40, and the last four to 0. Adding 8 makes the last two numbers multiply to 32.

3. Constraints

  • 0 <= num <= 100
  • 1 <= k <= 4 * 10$^4$
  • At most 4 * 10$^4$ calls are made in total to add and getProduct.
  • Each query has at least k previously added numbers.
  • The product of any contiguous sequence fits in a signed 32-bit integer.

4. Solutions

Prefix Product

n is the total number of calls to add
Time complexity: O(1) for initialization and getProduct; amortized O(1) for add
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class ProductOfNumbers {
public:
    ProductOfNumbers() {}

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

    int getProduct(int k) {
        const int n = prefix.size();
        if (k >= n) {
            return 0;
        }

        return prefix.back() / prefix[n - k - 1];
    }

private:
    vector<int> prefix{1};
};
comments powered by Disqus