LeetCode 1352 - Product of the Last K Numbers

Difficulty: 🟡 Medium
Topics: Array, Math, Design, Data Stream, Prefix Sum

Solution

Problem Understanding

This problem asks us to design a data structure that continuously processes a stream of integers and supports querying the product of the last k inserted numbers.

The ProductOfNumbers class starts with an empty sequence. Every time add(num) is called, a new integer is appended to the stream. Later, getProduct(k) must return the multiplication result of the most recent k numbers.

For example, if the stream currently contains:

[3, 0, 2, 5, 4]

then:

getProduct(2) returns 5 × 4 = 20
getProduct(3) returns 2 × 5 × 4 = 40
getProduct(4) returns 0 × 2 × 5 × 4 = 0

The challenge is that the stream grows dynamically, and queries may happen frequently. A naive implementation could recompute the product every time by iterating over the last k numbers, but the follow-up explicitly asks whether both operations can be made O(1).

The constraints are important:

At most 4 × 10⁴ calls are made to add and getProduct.
Each num is between 0 and 100.
The product of any contiguous subarray fits inside a 32-bit integer.

The biggest challenge is handling 0. Multiplication with zero resets the product, which means a straightforward prefix product division technique does not work unless zeros are carefully handled.

Some important edge cases immediately stand out:

Zero appears in the stream: any product range containing that zero becomes 0.
Consecutive zeros: multiple resets must be handled correctly.
k spans beyond the most recent zero: if a zero exists in the queried range, the answer must be 0.
Small streams: the problem guarantees k is always valid, meaning there are at least k numbers available.

Approaches

Brute Force Approach

The most direct solution is to store all inserted numbers in a list and compute the product manually whenever getProduct(k) is called.

When add(num) is called, we simply append the number to an array.

When getProduct(k) is requested, we iterate backward through the last k elements and multiply them together.

This works because it explicitly computes the required product from the exact numbers involved. Since multiplication is associative, iterating through the range guarantees the correct result.

However, this approach becomes inefficient because each query takes O(k) time. Since k can be as large as 4 × 10⁴, repeated queries can become expensive.

Optimal Approach, Prefix Products with Zero Reset

The key observation is that repeated multiplication over overlapping ranges is wasteful.

Instead of recalculating products repeatedly, we can maintain prefix products. Normally, if:

prefix[i] = product of first i elements

then the product of the last k numbers can be computed as:

prefix[n] / prefix[n-k]

This gives constant-time range product retrieval.

However, zeros complicate things because division by a prefix containing zero is impossible. The insight is that whenever a 0 appears, every product spanning that zero must be 0, so we can reset the prefix array.

We maintain a prefix product list starting with 1 as a sentinel:

[1]

For non-zero numbers:

prefix.append(prefix[-1] * num)

For zero:

prefix = [1]

Then, when answering getProduct(k):

If k >= len(prefix), it means the query spans across a zero, so return 0.
Otherwise:

prefix[-1] // prefix[-1-k]

This works in O(1) time for both operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	`O(k)` per query	`O(n)`	Stores stream and multiplies last `k` numbers each time
Optimal	`O(1)` per operation	`O(n)`	Uses prefix products and resets after zero

Algorithm Walkthrough

Initialize a prefix product list with a sentinel value 1.

This sentinel simplifies division calculations and avoids edge cases when computing products from the beginning of the sequence.

Example:

prefix = [1]

When add(num) is called, check whether num is zero.

If num == 0, reset the prefix array:

prefix = [1]

This effectively forgets everything before the zero because any range crossing the zero must evaluate to 0. 3. If num is non-zero, append the cumulative product.

Compute:

prefix.append(prefix[-1] * num)

Example:

stream: [2,5,4]

prefix:
[1]
[1,2]
[1,2,10]
[1,2,10,40]

When getProduct(k) is called, determine whether the range crosses a zero.

If:

k >= len(prefix)

then the requested range includes a zero, so return:

Otherwise, compute the product using division of prefix products.

Formula:

prefix[-1] // prefix[-1-k]

Example:

prefix = [1,2,10,40]

getProduct(2)

= 40 // 2
= 20

Why it works

The core invariant is that prefix[i] always stores the product of all numbers since the most recent zero. Therefore, for any valid range that does not cross a zero, division of prefix products correctly isolates the requested suffix product.

If the requested range crosses a zero, the prefix array length becomes too short because it was reset after the zero. Detecting this condition with k >= len(prefix) guarantees we correctly return 0.

Python Solution

class ProductOfNumbers:

    def __init__(self):
        self.prefix_products: list[int] = [1]

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

    def getProduct(self, k: int) -> int:
        if k >= len(self.prefix_products):
            return 0

        return (
            self.prefix_products[-1]
            // self.prefix_products[-1 - k]
        )

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

The implementation uses a single list called prefix_products. The list starts with 1, which acts as a sentinel value to simplify division.

In add, if the incoming number is zero, the list is reset. This reset is critical because any product that spans this zero must become zero, so previous products are no longer useful.

For non-zero values, the cumulative product is appended. Since multiplication is cumulative, this gives us a compact representation of products over suffixes.

In getProduct, we first check whether k exceeds the available prefix history. If it does, the requested range must cross a zero, so we return 0. Otherwise, we divide the latest cumulative product by the product just before the queried range.

Go Solution

type ProductOfNumbers struct {
	prefixProducts []int
}

func Constructor() ProductOfNumbers {
	return ProductOfNumbers{
		prefixProducts: []int{1},
	}
}

func (this *ProductOfNumbers) Add(num int) {
	if num == 0 {
		this.prefixProducts = []int{1}
		return
	}

	newProduct := this.prefixProducts[len(this.prefixProducts)-1] * num
	this.prefixProducts = append(this.prefixProducts, newProduct)
}

func (this *ProductOfNumbers) GetProduct(k int) int {
	if k >= len(this.prefixProducts) {
		return 0
	}

	lastIndex := len(this.prefixProducts) - 1

	return this.prefixProducts[lastIndex] /
		this.prefixProducts[lastIndex-k]
}

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(num);
 * param_2 := obj.GetProduct(k);
 */

The Go implementation follows the exact same logic as the Python version, but uses a slice for storing prefix products.

Instead of Python's dynamic list operations, Go uses append() to grow the slice. Resetting after a zero is done by assigning:

[]int{1}

Go integer division behaves exactly as needed here because all stored products are exact multiples of earlier prefix values, so no rounding issues occur.

Worked Examples

Example 1

Operations:

add(3)
add(0)
add(2)
add(5)
add(4)
getProduct(2)
getProduct(3)
getProduct(4)
add(8)
getProduct(2)

Operation	Prefix Products	Result
Initialize	`[1]`	-
`add(3)`	`[1,3]`	-
`add(0)`	`[1]`	-
`add(2)`	`[1,2]`	-
`add(5)`	`[1,2,10]`	-
`add(4)`	`[1,2,10,40]`	-
`getProduct(2)`	`[1,2,10,40]`	`40 // 2 = 20`
`getProduct(3)`	`[1,2,10,40]`	`40 // 1 = 40`
`getProduct(4)`	`[1,2,10,40]`	`0`, range crosses zero
`add(8)`	`[1,2,10,40,320]`	-
`getProduct(2)`	`[1,2,10,40,320]`	`320 // 10 = 32`

The reset after add(0) is the key behavior. It ensures that any query reaching past that point automatically returns 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(1)`	Both `add` and `getProduct` perform constant-time operations
Space	`O(n)`	Stores prefix products for non-zero values

The time complexity is constant because every operation involves only a few arithmetic operations and list accesses. No loops are required during queries.

The space complexity is linear in the number of inserted elements since we maintain one prefix value per non-zero number. In the worst case, when no zeros appear, the structure stores all inserted numbers as cumulative products.

Test Cases

# Provided example
obj = ProductOfNumbers()
obj.add(3)
obj.add(0)
obj.add(2)
obj.add(5)
obj.add(4)

assert obj.getProduct(2) == 20  # 5 * 4
assert obj.getProduct(3) == 40  # 2 * 5 * 4
assert obj.getProduct(4) == 0   # includes zero

obj.add(8)
assert obj.getProduct(2) == 32  # 4 * 8

# Single element
obj = ProductOfNumbers()
obj.add(7)
assert obj.getProduct(1) == 7  # only one element

# Multiple non-zero values
obj = ProductOfNumbers()
obj.add(2)
obj.add(3)
obj.add(4)

assert obj.getProduct(1) == 4   # last element
assert obj.getProduct(2) == 12  # 3 * 4
assert obj.getProduct(3) == 24  # full range

# Zero reset behavior
obj = ProductOfNumbers()
obj.add(5)
obj.add(6)
obj.add(0)
obj.add(2)
obj.add(3)

assert obj.getProduct(1) == 3  # last element
assert obj.getProduct(2) == 6  # 2 * 3
assert obj.getProduct(3) == 0  # crosses zero

# Consecutive zeros
obj = ProductOfNumbers()
obj.add(0)
obj.add(0)
obj.add(5)

assert obj.getProduct(1) == 5  # only recent number
assert obj.getProduct(2) == 0  # includes zero

# Large k after zero
obj = ProductOfNumbers()
obj.add(1)
obj.add(2)
obj.add(0)
obj.add(4)

assert obj.getProduct(2) == 0  # spans zero

# Multiplication by one
obj = ProductOfNumbers()
obj.add(1)
obj.add(1)
obj.add(1)

assert obj.getProduct(3) == 1  # product remains 1

Test	Why
Provided example	Validates core functionality
Single element	Tests smallest valid stream
Multiple non-zero values	Verifies prefix division logic
Zero reset behavior	Ensures zero handling works
Consecutive zeros	Tests repeated resets
Large `k` after zero	Confirms queries crossing zero return `0`
Multiplication by one	Validates neutral multiplication

Edge Cases

Query Range Includes a Zero

A major source of bugs is when the requested range spans a zero. A naive prefix division approach would fail because division involving zero is invalid.

For example:

[3, 0, 2, 5]
getProduct(3)

The answer must be 0 because the range includes 0. The implementation handles this correctly by resetting the prefix array whenever zero is inserted. Since the history before zero disappears, k >= len(prefix_products) detects this situation and returns 0.

Consecutive Zeros

Multiple zeros in a row can create subtle bugs if resets are not handled properly.

Example:

[0, 0, 5]

The implementation simply resets the prefix array each time a zero appears:

[1]
[1]
[1,5]

This ensures queries behave correctly without special-case logic.

Querying the Entire Valid Range

Suppose the stream contains:

[2, 3, 4]

Calling:

getProduct(3)

should return the product of all numbers. Without a sentinel value, index handling becomes error-prone. By storing an initial 1, the computation becomes:

24 // 1 = 24

which works naturally and avoids boundary bugs.