We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Product of the Last K Numbers

Difficulty: Medium

Problem Description

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream. Implement the ProductOfNumbers class with methods to add integers to the stream and get the product of the last k numbers.

Key Insights

  • The product of the last k numbers must be calculated efficiently.
  • Zeros in the stream reset the product, so they need to be handled specifically.
  • A data structure that allows quick access to the last k elements is required.

Space and Time Complexity

Time Complexity: O(1) for both add and getProduct methods.
Space Complexity: O(n) where n is the number of elements added to the stream.

Solution

To solve the problem, we can use a list to store the numbers in the stream. For the add method, we will append the new number to the list. For the getProduct method, we will iterate backwards from the end of the list to calculate the product of the last k numbers. To optimize for the follow-up question, we can maintain a prefix product array that allows us to compute the product in constant time, adjusting for zeros when necessary.

Code Solutions

class ProductOfNumbers:
    def __init__(self):
        self.nums = []
        self.prefix = [1]  # Prefix product array

    def add(self, num: int) -> None:
        self.nums.append(num)
        if num == 0:
            self.prefix = [1]  # Reset prefix upon adding zero
        else:
            # Update the prefix product
            self.prefix.append(self.prefix[-1] * num)

    def getProduct(self, k: int) -> int:
        if k > len(self.nums):
            return 0
        # Get the last k product using prefix array
        return self.prefix[-1] // self.prefix[-(k + 1)]  # Avoid division by zero
← Back to All Questions