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.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).
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1).
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Naive Approach with Array | Time Complexity: O(k). |
| Optimized Approach with Prefix Products | Time Complexity: O(1). |
Leetcode 1352. Product of the Last K Numbers • Fraz • 8,045 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