#1352

Medium

LeetCode Problem Workspace

Product of the Last K Numbers

Design a data structure to efficiently return the product of the last k numbers in a dynamic integer stream using prefix products.

array math design data stream prefix sum

Problem Statement

Implement a class ProductOfNumbers that allows adding numbers to a stream and retrieving the product of the last k numbers at any moment. The class must efficiently handle zero values in the stream without recomputing all products each time.

Design the following methods: add(int num) to append a new integer to the stream, and getProduct(int k) to return the product of the last k numbers. The stream values and queries will always result in products that fit within a 32-bit integer.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 <= 100
1 <= k <= 4 * 104
At most 4 * 104 calls will be made to add and getProduct.
The product of the stream at any point in time will fit in a 32-bit integer.

Solution Approach

Maintain Prefix Products Array

Store the cumulative product of all numbers in an array. Each add operation multiplies the last prefix product by the new number, and resets if the number is zero. This allows quick product computation for the last k numbers by dividing two prefix products.

Handle Zero Values Efficiently

Zeros break the multiplicative chain, so track indices of zeros separately. If a query includes a zero, return zero immediately. This prevents invalid division and ensures correctness without scanning the entire array.

Optimize getProduct Queries

Use the prefix products array and zero index tracking to calculate the product of the last k numbers in O(1) time. Divide the latest prefix product by the prefix product before the segment, or return zero if a zero falls within the last k elements.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Adding a number is O(1) as it updates the prefix products array and zero positions. getProduct queries are O(1) using the prefix array and zero index tracking. Space complexity is O(n) to store prefix products and zero indices for all numbers in the stream.

What Interviewers Usually Probe

Watch for zeros in the stream that reset cumulative products.
Ensure getProduct runs in constant time without looping over last k elements.
Expect discussion of edge cases with k larger than the current stream size.

Common Pitfalls or Variants

Common pitfalls

Dividing by zero without checking if the segment contains a zero.
Not updating prefix products correctly after adding a zero.
Mismanaging indices when the stream is shorter than k.

Follow-up variants

Compute sum instead of product for the last k numbers while still supporting zeros.
Support dynamic removal of numbers from the end and adjust prefix products accordingly.
Track the maximum product of any contiguous k-length subarray in a real-time stream.

FAQ

How do you handle zeros in the Product of the Last K Numbers problem?

Track zero positions in the stream and return zero for any getProduct query if a zero exists within the last k elements.

Can getProduct run faster than O(k) in this problem?

Yes, using prefix products and zero tracking, getProduct runs in O(1) without scanning the last k elements.

What happens if k is larger than the current number of elements?

Return the product of all available elements or zero if any zero exists within that range, ensuring correctness.

Why use an array of prefix products instead of recomputing each query?

It allows constant-time product calculation while efficiently handling zeros, preventing repeated multiplication of the same segment.

Does this problem relate to a common interview pattern?

Yes, it combines array manipulation with math, specifically prefix products, to optimize range-based calculations in streams.

terminal

Solution

Solution 1: Prefix Product

We initialize an array $s$, where $s[i]$ represents the product of the first $i$ numbers.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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)

Continue Practicing

#1442 count triplets that can form two arrays of equal xor #1248 count number of nice subarrays #1472 design browser history