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)
| |