Product of the Last K Numbers: Prefix Products with Zero Reset

Design a class ProductOfNumbers that supports two operations: add(num) appends a number to the back of a stream, and getProduct(k) returns the product of the last k numbers in the stream. You are guaranteed that the product of any contiguous subsequence will fit in a 32-bit integer.

This is LeetCode 1352: Product of the Last K Numbers, and it is a great example of how prefix products can be adapted to handle streaming data. The twist that makes this problem interesting is how you deal with zeroes.

Why this problem matters

Prefix sums are one of the most common patterns in array problems. This problem takes the same idea and applies it to products, then adds two complications: the data arrives as a stream (you do not know all the numbers up front), and zeroes can appear at any time. Zeroes are poison for products because once a zero enters the running product, every subsequent product that includes it becomes zero.

Learning to handle that zero-reset cleanly is the real lesson here. It shows up again in problems like "Maximum Product Subarray" and any context where you maintain running computations that can be invalidated by a single bad value.

The approach

Maintain an array called prefix that stores cumulative products. Start with prefix = [1]. When you call add(num):

• If num is not zero, append prefix[-1] * num to the array. Each entry at index i stores the product of all numbers added since the last zero (or since initialization).
• If num is zero, reset prefix back to [1]. Any future product that reaches back past this zero is automatically zero.

For getProduct(k):

• If k >= len(prefix), it means the window of k numbers includes (or goes past) a zero. Return 0.
• Otherwise, return prefix[-1] // prefix[-k - 1]. This works because prefix[-1] is the product of all numbers since the last zero, and prefix[-k - 1] is the product of everything before the last k numbers. Dividing cancels out the prefix, leaving just the product of the last k.

The solution

class ProductOfNumbers:
    def __init__(self):
        self.prefix = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix = [1]
        else:
            self.prefix.append(self.prefix[-1] * num)

    def getProduct(self, k: int) -> int:
        if k >= len(self.prefix):
            return 0
        return self.prefix[-1] // self.prefix[-k - 1]

The constructor initializes prefix with a single 1. This base element serves as the multiplicative identity: when you compute the first real product, you multiply 1 * num, which is just num.

The add method checks for zero first. If the incoming number is zero, you throw away the entire prefix and start fresh. Any getProduct call that tries to look back past this point will see that k >= len(prefix) and return 0. If the number is nonzero, you extend the running product by multiplying the last prefix value by the new number.

The getProduct method uses the standard prefix trick. The product of elements from index n - k to n - 1 is prefix[n] / prefix[n - k]. In Python list terms, prefix[-1] is the total product and prefix[-k - 1] is the product of everything before the window. The length check catches the case where a zero was added within the last k numbers.

Visual walkthrough

Let's trace through the full sequence: add(3), add(0), add(2), add(5), add(4), then getProduct(2), getProduct(3), and getProduct(4).

The zero at step 3 is the critical moment. Instead of carrying a zero through the prefix array (which would make every future product zero), you reset the array entirely. This way, every nonzero product after the reset is computed cleanly, and the length check in getProduct handles the case where the query window crosses the zero boundary.

Complexity analysis

Time for add is O(1). You either reset the array (constant time) or append one element (amortized constant time). getProduct is O(1) because it performs one comparison and one division.

Space is O(n) where n is the number of elements added since the last zero. In the worst case (no zeroes ever added), the prefix array grows to the total number of add calls. In practice, each zero trims it back down.

The building blocks

1. Prefix products

The core idea is the same as prefix sums, but with multiplication. A prefix product array lets you compute the product of any contiguous subarray in O(1) time by dividing the product at the right endpoint by the product at the left endpoint.

# prefix[i] = nums[0] * nums[1] * ... * nums[i-1]
# product(nums[l..r]) = prefix[r+1] / prefix[l]

You will see this pattern in "Product of Array Except Self" (LeetCode 238), where you build both a left-product and a right-product array. The underlying math is identical: division undoes multiplication, so you can "subtract" a prefix by dividing.

2. Zero-reset technique

When a value that invalidates your running computation appears, reset the state instead of carrying the invalid value forward. In this problem, multiplying by zero would permanently contaminate the prefix array. By resetting to [1], you get a clean slate, and the length of the new array tells you exactly how far back you can look without hitting a zero.

This "reset on invalid" pattern appears in other problems too. In "Maximum Product Subarray," you reset your running min and max when you encounter a zero. The principle is the same: detect the poisoning element and start fresh rather than trying to work around it.

Edge cases

Before submitting, think through these scenarios:

• All zeroes: every add(0) resets the prefix. Every getProduct(k) returns 0 because k >= len(prefix) is always true (prefix is always [1]).
• No zeroes: the prefix array grows indefinitely. getProduct always succeeds with the division formula.
• getProduct(1): returns the last number added. prefix[-1] / prefix[-2] simplifies to the most recent value.
• Zero followed immediately by getProduct(1): after add(0), prefix is [1]. getProduct(1) checks 1 >= 1, which is true, so it returns 0. This is correct because the last number added was 0.
• Large products: the problem guarantees results fit in a 32-bit integer, so you do not need to worry about overflow in Python. In other languages, you may need to use 64-bit integers for the prefix array.
• Single element stream: add(5) then getProduct(1) returns 5 / 1 = 5.

From understanding to recall

You have seen how prefix products with a zero-reset handle streaming product queries in O(1) time. The code is short and the logic is clean. But this problem tests two separate skills: knowing the prefix product technique and knowing the zero-reset trick. Under interview pressure, it is easy to forget one or the other.

The common mistakes are: forgetting to handle zero (leading to division-by-zero errors or permanent zero contamination), off-by-one errors in the getProduct index calculation, and forgetting the length check that catches queries spanning a zero. These are not conceptual gaps. They are pattern-recall gaps, and spaced repetition is how you close them.

Practice writing the add method (with its zero check) and the getProduct method (with its length check and division) separately, from memory, at increasing intervals. After a few rounds, the two-branch structure of add and the two-case structure of getProduct become automatic. You see "streaming product query" in a problem description, and the prefix-with-reset template flows out without hesitation.

Related posts

• Product of Array Except Self - The classic prefix product problem that builds left and right product arrays
• Range Sum Query - Immutable - The additive version of prefix queries, foundational for understanding the prefix trick
• Design HashMap - Another design-class problem that tests your ability to implement a clean data structure interface

CodeBricks breaks Product of the Last K Numbers into its prefix product and zero-reset building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a prefix product problem shows up in your interview, you do not think about it. You just write it.