LeetCode Solutions Blog

Product of the Last K Numbers

Number: 1477

Difficulty: Medium

Paid? No

Problem Description

Design a data structure that accepts a stream of integers and returns the product of the last k numbers in the stream. The operations include adding a number to the stream and retrieving the product of the last k numbers. Note that any contiguous sequence product will fit in a 32-bit integer. Special attention is needed for handling zeros, which effectively reset the product accumulation.

Key Insights

Use a prefix product list to quickly compute the product of any contiguous subarray in O(1) time.
When a zero is encountered, it resets any cumulative product; thus, the prefix product list can be restarted.
For getProduct(k), if k is larger than the number of elements since the last zero, the product must be zero.
The approach provides both add and getProduct operations in O(1) time (amortized).

Space and Time Complexity

Time Complexity: O(1) for both add and getProduct operations. Space Complexity: O(n) where n is the number of elements added (until reset due to a zero).

Solution

We maintain a list of prefix products that stores the cumulative product of the numbers after the most recent zero. When adding a new number:

If the number is zero, we reset the prefix product list.
Otherwise, we multiply the new number with the last prefix product (or set it as the first element if the list is empty).

For getProduct(k), if k is greater than the current length of the prefix product list, it means a zero was encountered within the last k numbers and the product is zero. Otherwise, we compute the result by dividing the last prefix product by the prefix product located at the index from the end that corresponds to k numbers.

Code Solutions

# Python implementation with line-by-line comments

class ProductOfNumbers:
    def __init__(self):
        # Initialize the list to store prefix products.
        self.prefix_products = []  # This list will store cumulative products since the last zero.

    def add(self, num: int) -> None:
        # If the added number is zero, reset the prefix product list.
        if num == 0:
            self.prefix_products = []
        else:
            # If prefix_products is empty, the current number is the product.
            if not self.prefix_products:
                self.prefix_products.append(num)
            else:
                # Multiply the new number with the last product in the list.
                self.prefix_products.append(self.prefix_products[-1] * num)

    def getProduct(self, k: int) -> int:
        # If k is greater than the length of prefix_products, a zero must be in the range.
        if k > len(self.prefix_products):
            return 0
        
        # When k equals the length of the prefix product list, the product of last k numbers is the entire product.
        if k == len(self.prefix_products):
            return self.prefix_products[-1]
        
        # Otherwise, return the ratio of the current product and the product before the last k numbers.
        # Use integer division because values are integers.
        return self.prefix_products[-1] // self.prefix_products[-k - 1]

# Example usage:
# productOfNumbers = ProductOfNumbers()
# productOfNumbers.add(3)
# productOfNumbers.add(0)
# productOfNumbers.add(2)
# productOfNumbers.add(5)
# productOfNumbers.add(4)
# print(productOfNumbers.getProduct(2)) # Output: 20
# print(productOfNumbers.getProduct(3)) # Output: 40
# print(productOfNumbers.getProduct(4)) # Output: 0
# productOfNumbers.add(8)
# print(productOfNumbers.getProduct(2)) # Output: 32