Problem Informations

• Problem Index: 1352
• Problem Link: Product of the Last K Numbers
• Topics: Array, Math, Design, Data Stream, Prefix Sum

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:

• ProductOfNumbers() Initializes the object with an empty stream.
• void add(int num) Appends the integer num to the stream.
• int getProduct(int k) Returns the product of the last $k$ numbers in the current list. You can assume that always the current list has at least $k$ numbers.

The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:

Input

["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output

[null,null,null,null,null,null,20,40,0,null,32]

Explanation

ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32

Constraints:

• $0 \leq num \leq 100$
• $1 \leq k \leq 4 \times 10^4$
• At most $4 \times 10^4$ calls will be made to add and getProduct.
• The product of the stream at any point in time will fit in a 32-bit integer.

Follow-up: Can you implement both GetProduct and Add to work in $O(1)$ time complexity instead of $O(k)$ time complexity?

Intuition

The problem requires designing a data structure to efficiently manage a stream of integers and compute the product of the last $k$ integers. The challenge lies in efficiently updating and querying the product of the most recent $k$ elements despite dynamic updates to the list of integers, particularly with respect to zeros, which disrupt multiplicative continuity. The key is efficiently maintaining the information necessary to compute these products without recomputing them from scratch upon every query.

Approach

The solution involves using a dynamic programming-like approach where a vector named prefixProduct stores cumulative products of the numbers in the stream. Specifically, prefixProduct[i] holds the product of the first $i$ numbers, with prefixProduct[0] initialized to 1 to simplify calculations.

1. Initialization:

   • We initialize prefixProduct with a single element 1. This serves as the base case for computing cumulative products, allowing us to handle product computations uniformly.

2. Adding a Number (add method):

   • When a new number num is added, the behavior branches based on whether num is zero or non-zero.
   • If num is zero: Zeros break the continuity of product series. Therefore, the entire prefixProduct is reset except for the initial 1. This indicates that any product query including this zero should result in zero.
   • If num is non-zero: The cumulative product is extended by appending prefixProduct.back() * num to prefixProduct, thereby maintaining a running product up to the current number.

3. Retrieving Product (getProduct method):

   • To retrieve the product of the last $k$ numbers, we need to assess whether the product series includes a reset point.
   • If $k \geq \text{prefixProduct.size()}$: This indicates there was a zero in the past $k$ elements, as the prefixProduct size is reset upon encountering a zero. In this scenario, the product is zero because a zero is included in the range.
   • Otherwise: The product of the last $k$ numbers is computed as the division of the cumulative product of all numbers up to the current point by the cumulative product just before the last $k$ numbers. This can be expressed as: $$ \text{product} = \frac{\text{prefixProduct.back()}}{\text{prefixProduct}[\text{prefixProduct.size()} - k - 1]} $$

Using this efficient handling of the product series and careful management of zero occurrences, both add and getProduct operations can be performed in $O(1)$ time complexity. This approach takes advantage of the properties of multiplication and division within the context of a cumulative product array to maintain efficiency despite dynamic updates to the stream.

Code

C++

class ProductOfNumbers {
public:
    // Vector to store the prefix product of the numbers
    vector<int> prefixProduct{1};

    // Constructor initializes the object with an empty stream
    ProductOfNumbers() {}

    // Adds a number to the stream
    void add(int num) {
        if (num == 0) {
            // If the number is zero, reset the prefix product list
            prefixProduct.clear();
            prefixProduct.emplace_back(1);
        } else {
            // Add the product of the last number in the list and the current number
            prefixProduct.emplace_back(prefixProduct.back() * num);
        }
    }

    // Retrieves the product of the last k numbers in the stream
    int getProduct(int k) {
        // If k is larger than the size of prefixProduct, it means there was a zero
        // in the last k numbers, so the product is 0
        return (k >= prefixProduct.size()) ? 0 : prefixProduct.back() / prefixProduct[prefixProduct.size() - k - 1];
    }
};

/**
    * Your ProductOfNumbers object will be instantiated and called as such:
    * ProductOfNumbers* obj = new ProductOfNumbers();
    * obj->add(num);
    * int param_2 = obj->getProduct(k);
    */

Python

class ProductOfNumbers:
    # List to store the prefix product of the numbers
    prefixProduct = [1]

    # Constructor initializes the object with an empty stream
    def __init__(self):
        pass

    # Adds a number to the stream
    def add(self, num: int):
        if num == 0:
            # If the number is zero, reset the prefix product list
            self.prefixProduct.clear()
            self.prefixProduct.append(1)
        else:
            # Add the product of the last number in the list and the current number
            self.prefixProduct.append(self.prefixProduct[-1] * num)

    # Retrieves the product of the last k numbers in the stream
    def getProduct(self, k: int) -> int:
        # If k is larger than the size of prefixProduct, it means there was a zero
        # in the last k numbers, so the product is 0
        return 0 if k >= len(self.prefixProduct) else self.prefixProduct[-1] // self.prefixProduct[len(self.prefixProduct) - k - 1]


# Example of how the class would be used:
# productOfNumbers = ProductOfNumbers()
# productOfNumbers.add(3)
# productOfNumbers.add(0)
# productOfNumbers.add(2)
# productOfNumbers.add(5)
# productOfNumbers.add(4)
# print(productOfNumbers.getProduct(2)) # Outputs 20
# print(productOfNumbers.getProduct(3)) # Outputs 40
# print(productOfNumbers.getProduct(4)) # Outputs 0
# productOfNumbers.add(8)
# print(productOfNumbers.getProduct(2)) # Outputs 32

Complexity

• Time complexity: The add(int num) method has a time complexity of $O(1)$ because it involves a constant number of operations regardless of the size of the input or the prefix product list. The getProduct(int k) method also has a time complexity of $O(1)$, as it involves a constant number of arithmetic operations and conditional checks. Therefore, both methods work in constant time.

• Space complexity: The space complexity is $O(n)$, where $n$ is the number of calls made to the add method. This is because the prefixProduct vector grows linearly with the number of added elements, as it stores one additional element for each add call.