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.Problem Overview: Design a data structure that supports two operations on a stream of integers: add(num) and getProduct(k). The second operation returns the product of the last k numbers added to the stream. The challenge is answering queries efficiently even when the stream grows large.
Approach 1: Naive Approach with Array (Add: O(1), Query: O(k) time, O(n) space)
Store every incoming number in a dynamic array. When getProduct(k) is called, iterate over the last k elements and multiply them together. The logic is straightforward: compute the product on demand using a simple loop from n - k to n - 1. This approach uses an array to keep the stream and requires no preprocessing.
The downside appears when queries are frequent or k becomes large. Each query scans up to k elements, making the worst‑case time O(k). For a long stream with many queries, this quickly becomes inefficient. Still, it works well for small inputs or when query frequency is low.
Approach 2: Prefix Products (Add: O(1), Query: O(1) time, O(n) space)
The optimized solution stores cumulative prefix products. Maintain a list where prefix[i] represents the product of all numbers from the start of the stream up to index i. When a new number arrives, append prefix[last] * num. To compute the product of the last k numbers, divide the current prefix product by the prefix value k positions earlier.
The key complication is handling zeros. If a zero appears in the stream, any product spanning that position becomes zero. The fix is simple: reset the prefix list whenever a zero is added. If the query asks for more elements than currently stored after the last zero, return 0.
This design transforms each query into constant time arithmetic. It works because multiplication over a range can be reconstructed from two prefix values, similar to prefix sums but using products. The pattern commonly appears in math and data stream problems where repeated range queries must be fast.
Recommended for interviews: Interviewers expect the prefix product approach. The brute force array method demonstrates baseline reasoning, but the optimized design shows you recognize prefix techniques and can adapt them to streaming data with edge cases like zeros. Achieving O(1) query time is the key signal of a strong solution.
In this approach, we maintain an array that stores all elements added so far. When retrieving the product of the last k elements, we iterate from the end of the array, multiplying the last k elements to compute the result. This approach can be simple but may lead to more complex implementations and inefficient performance for large values of k.
This solution maintains an array where each call to add stores a new element. The method getProduct starts from the last added index and traverses backward to find the product of the last k numbers. Space complexity is O(n) for storing numbers, and time complexity for the getProduct function is O(k).
Time Complexity: O(k).
Space Complexity: O(n).
To enhance efficiency, we calculate prefix products of the stream. Instead of storing all numbers, we store the cumulative product up to each index. Each time a zero is added, we reset these products because it invalidates previous products for future calculations. This allows us to retrieve the product of the last k numbers in constant time.
In this C solution, we use an array to store prefix products. On adding a zero, we reset the starting size, thus invalidating previous products. Computation in getProduct uses division to determine the product of the last k numbers. It requires O(1) time to compute the product, and O(n) space for storage in prefix products.
Time Complexity: O(1).
Space Complexity: O(n).
We initialize an array s, where s[i] represents the product of the first i numbers.
When calling add(num), we judge whether num is 0. If it is, we set s to [1]. Otherwise, we multiply the last element of s by num and add the result to the end of s.
When calling getProduct(k), we now judge whether the length of s is less than or equal to k. If it is, we return 0. Otherwise, we return the last element of s divided by the k + 1th element from the end of s. That is, s[-1] / s[-k - 1].
The time complexity is O(1), and the space complexity is O(n). Where n is the number of times add is called.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Naive Approach with Array | Time Complexity: O(k). |
| Optimized Approach with Prefix Products | Time Complexity: O(1). |
| Prefix Product | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Array Multiplication | Add: O(1), Query: O(k) | O(n) | Useful for small streams or when query operations are rare |
| Prefix Products with Zero Reset | Add: O(1), Query: O(1) | O(n) | Best for frequent queries and large data streams |
Leetcode 1352. Product of the Last K Numbers • Fraz • 8,321 views views
Watch 9 more video solutions →Practice Product of the Last K Numbers with our built-in code editor and test cases.
Practice on FleetCode