Leetcode #1352: Product of the Last K Numbers
In this guide, we solve Leetcode #1352 Product of the Last K Numbers in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Design, Array, Math, Data Stream, Prefix Sum
Intuition
Range queries become simple once we precompute cumulative sums.
We can transform subarray conditions into prefix comparisons.
Approach
Compute prefix sums and use a map to find matching prefixes.
This avoids nested loops while keeping the logic clear.
Steps:
- Compute prefix sums.
- Use a map to find valid ranges.
- Update the answer.
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
Python Solution
class ProductOfNumbers:
def __init__(self):
self.s = [1]
def add(self, num: int) -> None:
if num == 0:
self.s = [1]
return
self.s.append(self.s[-1] * num)
def getProduct(self, k: int) -> int:
return 0 if len(self.s) <= k else self.s[-1] // self.s[-k - 1]
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.