Product of the Last K Numbers - Video Solutions

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.