Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.
Implement the ProductOfNumbers class:
ProductOfNumbers() Initializes the object with an empty stream.void add(int num) Appends the integer num to the stream.int getProduct(int k) Returns the product of the last k numbers in the current list. You can assume that always the current list has at least k numbers.The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
Example:
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 ProductOfNumbers productOfNumbers = new ProductOfNumbers(); productOfNumbers.add(3); // [3] productOfNumbers.add(0); // [3,0] productOfNumbers.add(2); // [3,0,2] productOfNumbers.add(5); // [3,0,2,5] productOfNumbers.add(4); // [3,0,2,5,4] productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20 productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40 productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0 productOfNumbers.add(8); // [3,0,2,5,4,8] productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32
Constraints:
0 <= num <= 1001 <= k <= 4 * 1044 * 104 calls will be made to add and getProduct.The key challenge in #1352 Product of the Last K Numbers is efficiently computing the product of the last k elements from a continuously growing data stream. A naive approach would recompute the product every time a query is made, which takes O(k) time and becomes inefficient for frequent queries.
A better strategy is to maintain a prefix product array. Each time a number is added, store the cumulative product up to that index. When asked for the product of the last k numbers, divide the current prefix product by the prefix product k positions earlier. This allows queries to be answered in constant time.
Special care is needed when encountering 0. Since any product including zero becomes zero, the prefix structure should reset when a zero appears. By restarting the prefix list after zeros, we ensure valid division-based queries. This design supports fast updates and queries, making it ideal for data stream scenarios.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive product calculation | Add: O(1), Query: O(k) | O(n) |
| Prefix product with reset on zero | Add: O(1), Query: O(1) | O(n) |
Fraz
Use these hints if you're stuck. Try solving on your own first.
Keep all prefix products of numbers in an array, then calculate the product of last K elements in O(1) complexity.
When a zero number is added, clean the array of prefix products.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
When a zero is added, the prefix product sequence must be reset because division-based queries would otherwise break. After a zero, only numbers added afterward should be considered in future product calculations.
Yes, this type of data stream and prefix-product design problem is common in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of prefix computations, edge cases like zeros, and efficient query handling.
A dynamic array or list storing prefix products works best for this problem. It allows efficient append operations and constant-time product queries using division between prefix values.
The optimal approach uses a prefix product array that stores cumulative products of inserted numbers. The product of the last k numbers can be obtained by dividing two prefix values. This allows constant time queries while handling zeros by resetting the prefix list.