Product of the Last K Numbers

Medium

Target

1 view

Topics:

ArraysSliding Windows

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 <= num <= 100
1 <= k <= 4 * 10⁴
At most 4 * 10⁴ 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?

Try coding it in LeetCode

Product of the Last K Numbers

Medium

Target

1 view

Topics:

ArraysSliding Windows

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 <= num <= 100
1 <= k <= 4 * 10⁴
At most 4 * 10⁴ 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?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the input number 'num' and the value 'k'?
What should the `getProduct(int k)` method return if 'k' is greater than the number of elements added so far?
Can the stream of numbers contain zero, and if so, how should that be handled when calculating the product?
Are there any memory constraints I should be aware of, considering the stream of numbers could potentially be very large?
Is the `add(int num)` method expected to be called significantly more often than the `getProduct(int k)` method, or vice versa?

Brute Force Solution

Approach

The brute force method for this problem means we're going to calculate the product every time we need it, without saving any previous results. We will keep a running record of all the numbers we've seen, and compute the result using only that record.

Here's how the algorithm would work step-by-step:

Keep a list of all the numbers we've seen so far.
When a new number comes in, add it to the end of the list.
When asked for the product of the last 'k' numbers, take the last 'k' numbers from the end of the list.
Multiply those 'k' numbers together to get the product.
Return the resulting product.

Code Implementation

class ProductOfNumbers:

    def __init__(self):
        self.numbers_list = []

    def add(self, number: int) -> None:
        # Append the new number to the list of numbers.
        self.numbers_list.append(number)

    def getProduct(self, k: int) -> int:
        # Extract the last 'k' numbers from the list.
        last_k_numbers = self.numbers_list[-k:]

        product_of_last_k_numbers = 1
        # Calculate the product of the last 'k' numbers.
        for number in last_k_numbers:
            product_of_last_k_numbers *= number

        return product_of_last_k_numbers

Big(O) Analysis

Time Complexity

O(k) – The add method is O(1) since it simply appends to a list. The getProduct method iterates through the last k elements of the list to calculate the product. Thus, the time complexity of getProduct is directly proportional to k, the number of elements to consider. Therefore, the overall time complexity for getProduct is O(k).

Space Complexity

O(N) – The brute force method maintains a list of all numbers seen so far. In the worst-case scenario, we will store every number that has been added, resulting in a list that grows linearly with the number of add operations. Therefore, we are using an auxiliary data structure, a list, to store up to N numbers, where N is the number of add operations. The space required is directly proportional to N, so the auxiliary space complexity is O(N).

Optimal Solution

Approach

Instead of recalculating the product every time, the smart approach is to keep a running record of products. This way, you can quickly find the product of the last 'k' numbers by using division with the precomputed products.

Here's how the algorithm would work step-by-step:

Keep a list of the cumulative products as each new number arrives.
If a zero arrives, reset the list because any product involving zero is zero. Start a fresh list with 1.
To find the product of the last 'k' numbers, divide the latest cumulative product by the cumulative product from 'k' steps ago.
Handle the edge case where 'k' is larger than the number of numbers seen so far. In this case, return zero because we don't have enough numbers to form the product.
Also, if the cumulative product from 'k' steps ago is zero, return zero to avoid division by zero.

Code Implementation

class ProductOfNumbers:

    def __init__(self):
        self.cumulative_products = [1]

    def add(self, number):
        if number == 0:
            # Reset list on zero because all future products are zero.
            self.cumulative_products = [1]

        else:
            self.cumulative_products.append(self.cumulative_products[-1] * number)

    def getProduct(self, k_numbers):
        if k_numbers >= len(self.cumulative_products):
            # Not enough numbers to form product
            return 0

        divisor_index = len(self.cumulative_products) - k_numbers - 1

        # Avoid division by zero if a zero exists in the last K numbers
        if self.cumulative_products[divisor_index] == 0:
            return 0

        return self.cumulative_products[-1] // self.cumulative_products[divisor_index]

Big(O) Analysis

Time Complexity

O(1) – The add operation appends a new element to the list, which takes O(1) time on average. The getProduct operation performs a constant number of calculations: list access and division. Since the operations do not depend on the number of elements added (n), the time complexity for both add and getProduct is O(1). The storage complexity however would be O(n), because we are storing a prefix product for each number added.

Space Complexity

O(N) – The algorithm maintains a list of cumulative products. In the worst-case scenario, when no zero arrives in the stream of numbers, the list will store the cumulative product of every number added so far. Therefore, the auxiliary space required grows linearly with the number of numbers added (N), where N is the total number of add operations called. This running record of products constitutes the dominant space usage. The algorithm uses O(N) auxiliary space.

Edge Cases

Case	How to Handle
Adding zero to the stream.	Reset the product array because any product involving zero becomes zero.
Requesting product of more numbers than added so far (k > size of stream).	Return 0 as no valid product can be computed given the constraint.
Large number of add operations, potentially exceeding memory limits.	The solution needs to be space optimized, for example only keep prefix products, or use an alternative data structure.
Large input numbers potentially leading to integer overflow in the product calculation.	Use a larger data type such as long or handle the overflow and return a specific error value.
Multiple consecutive zeros are added to the stream.	The product array needs to be reset for each zero encountered.
k is zero.	Return 1 as the product of no numbers is typically defined as 1.
Negative numbers in the stream.	The product array should handle negative numbers correctly as a negative times a negative is a positive.
Very large k, approaching the maximum integer value.	Ensure the solution doesn't run into integer overflow issues when handling such a large k value and that the implementation scales to such large values.