How to Solve Product of the Last K Numbers

This problem requires tracking cumulative products to answer queries about the last k numbers in O(1) time. Maintaining an array of prefix products allows each add operation to update the state efficiently while handling zeros correctly. Using this method, getProduct queries can quickly calculate results without iterating through the last k numbers, ensuring optimal performance for large streams.

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

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.

How GhostInterview Helps

• Automatically generates efficient prefix product updates and zero handling logic for any input stream.
• Validates that getProduct queries correctly return O(1) results with correct edge-case handling.
• Highlights potential pitfalls in division and stream boundaries to prevent common mistakes.

Topic Pages

• Array
• Math
• Design
• Data Stream
• Prefix Sum

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.