1352. Product of the Last K Numbers

MediumDesignQueueArrayMathData Stream
Leetcode Link

Problem Description

The given problem presents us with a scenario where we need to continuously monitor a stream of integers and have the ability to compute the product of the last 'k' numbers in the stream at any point. We are required to implement a ProductOfNumbers class that can:

  1. Be initialized without any numbers in the stream.
  2. Support appending numbers to the end of the stream.
  3. Calculate the product of the last 'k' numbers in the stream.

The constraints ensure that we will not face integer overflow issues since the product will always fit into a 32-bit integer, and the numbers added are within the range 0 to 100. The problem statement specifies that there will be a maximum of 40,000 calls to both add and getProduct methods which hints at the necessity for an efficient solution to handle large input streams.

Intuition

The straightforward solution would be to multiply the last 'k' numbers in the stream every time getProduct is called. However, this would not be efficient since the same products could be recalculated many times for different calls to getProduct.

A more efficient approach is to maintain a prefix product for the stream. The key insight here is that the product of any contiguous segment of the stream can be quickly calculated using the division of two prefix products.

To realize this solution, we maintain a list initialized with a single element, 1, which signifies an empty product (since the product of zero numbers is 1). Whenever a new number is added to the stream that is not zero, we append the product of this number and the last element in the list (which represents the product of all numbers up to that point). When zero is added to the stream, it invalidates all previous products, so we reset the list to its initial state containing just the one element.

For retrieving the product of the last 'k' numbers, we simply find the ratio of the last element in the list to the element that is k indices before the last element. We need to handle the case where a zero has been added within the last 'k' integers, in which case the product should be zero. We check this by comparing the length of the list with k; if the list is not long enough after adding zeros, it means there was a zero in the last 'k' elements, and we return 0.

Learn more about Queue, Math and Data Stream patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

To implement the solution, we utilize the concept of prefix products. Here is a breakdown of this approach and how we use it:

Data Structure:

  • We employ a list (self.s) as a primary data structure, which starts with one element [1] representing the product of zero numbers.

Adding a Number (add method):

  • When a non-zero number is added to the stream, we multiply the most recently added number (the last element in self.s) by the new number and append the result to the list. This maintains the prefix product for the entire stream.
  • In case the number 0 is added, we reset self.s to [1] because the product of any range including zero is zero, and thus all previous products become irrelevant.

Getting Product (getProduct method):

  • To get the product of the last k numbers, we check if our list self.s has enough elements to cover k numbers without encountering a zero. We do this by checking if len(self.s) <= k.
  • If the list is too short, this means a zero was added within the last k elements, and hence we return 0.
  • If the list is long enough, we use the property that the product of the last k numbers can be calculated by taking the k+1-th most recent element from the end of the list and dividing the last element of the list by this k+1-th element. In code, this is self.s[-1] // self.s[-k - 1].

By maintaining a running product, the algorithm allows for constant-time retrieval of the last k products, thereby making the operation efficient. It is assumed that all operations of multiplication and division with respect to the product retrieval will always result in integer values fitting in a 32-bit integer variable, as per the constraints of the problem.

Example:

Consider self.s = [1, 3, 5, 15] (implicit products of 1, 3, 32, 32*5), if we want to get the product of the last 2 numbers:

  • We would use self.s[-1] // self.s[-2 - 1], which translates to 15 // 3 = 5, the product of the last 2 numbers, 2 and 5.

This elegant solution avoids the need for repeated multiplication and directly uses the power of division and prefix products to provide the answers efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Example Walkthrough

Let's go through a small example to illustrate the solution approach:

  1. Initialize the ProductOfNumbers class. The internal list self.s starts with [1], indicating that the product of zero numbers is 1.

    • self.s = [1]

  2. Call the add method with the number 2. Since 2 is not zero, multiply the last element in self.s by 2 which is 1*2=2 and append it to self.s.

    • self.s = [1, 2]

  3. Add another number, say 5, through the add method. Multiply the last element in self.s by 5 which is 2*5=10 and append it.

    • self.s = [1, 2, 10]

  4. Add number 0. Adding 0 resets self.s because any product including zero is zero.

    • self.s = [1]

  5. Now, add the number 4 to the stream. We append 1*4=4 to self.s.

    • self.s = [1, 4]

  6. Next, we add 6 to the stream. We append 4*6=24 to self.s.

    • self.s = [1, 4, 24]

  7. Assume at this point we want to retrieve the product of the last 2 numbers. Since len(self.s) = 3 is greater than k = 2, we proceed with the division: self.s[-1] // self.s[-2 - 1] which translates to 24 // 4 = 6. Thus, getProduct(2) returns 6, which is the product of 4 and 6.

    • getProduct(2) = 6

  8. However, if we want to retrieve the product of the last 4 numbers, since adding zero has reset the list and we only have 2 numbers after that (4 and 6), we return 0 because it's not possible to have a product for the last 4 numbers.

    • getProduct(4) = 0

Through this example, you can see how efficient the solution is. It prevents recalculating products with every call to getProduct, thanks to the power of prefix products and the efficient handling of zeros in the stream.

Solution Implementation

1class ProductOfNumbers:
2    def __init__(self):
3        # Initialize a list with one element '1' to represent the prefix product
4        self.prefix_products = [1]
5
6    def add(self, num: int) -> None:
7        # Adds the number to the sequence of numbers
8        if num == 0:
9            # If the number is zero, reset the list since any subsequent product will be zero
10            self.prefix_products = [1]
11        else:
12            # Calculate the new product by multiplying the last product in the list with the new number
13            self.prefix_products.append(self.prefix_products[-1] * num)
14
15    def getProduct(self, k: int) -> int:
16        # Returns the product of the last k numbers in the sequence
17        if len(self.prefix_products) <= k:
18            # If k is greater than or equal to the number of elements, the product is zero
19            return 0
20        else:
21            # Otherwise, return the product of the last k numbers
22            # by dividing the last prefix product by the product at (n-k-1)th position
23            return self.prefix_products[-1] // self.prefix_products[-k - 1]
24
25
26# Usage
27# Initialize the object
28obj = ProductOfNumbers()
29
30# Add numbers with the add method
31obj.add(3)  # Sequence is now: [3]
32obj.add(0)  # Sequence is now: [1] because a zero resets everything
33obj.add(2)  # Sequence is now: [1, 2]
34obj.add(5)  # Sequence is now: [1, 2, 5]
35obj.add(4)  # Sequence is now: [1, 2, 5, 4]
36
37# Get the product of the last k numbers
38print(obj.getProduct(2))  # Output: 20, since the product of last 2 numbers (5, 4) is 20
39print(obj.getProduct(3))  # Output: 40, since the product of the last 3 numbers (2, 5, 4) is 40
40print(obj.getProduct(4))  # Output: 0, since k>= the number of elements after the last reset (when 0 was added)
41
1import java.util.ArrayList;
2import java.util.List;
3
4class ProductOfNumbers {
5    private List<Integer> prefixProducts;  // List to store the prefix products.
6
7    // Constructor initializes the data structure with a single '1'.
8    public ProductOfNumbers() {
9        prefixProducts = new ArrayList<>();
10        prefixProducts.add(1);
11    }
12
13    // Adds a number to the list, handling multiplication and the case when zero is added.
14    public void add(int num) {
15        if (num == 0) {
16            // If the number is zero, the product of all numbers will be zero.
17            // Clear the list and start anew with a single '1'.
18            prefixProducts.clear();
19            prefixProducts.add(1);
20        } else {
21            // Multiply the last element by 'num' to get the new product and add it to the list.
22            int lastProduct = prefixProducts.get(prefixProducts.size() - 1);
23            prefixProducts.add(lastProduct * num);
24        }
25    }
26
27    // Returns the product of the last 'k' numbers added to the list.
28    public int getProduct(int k) {
29        int n = prefixProducts.size();
30        // If 'k' is greater than or equal to the size, all the elements include a zero, return 0.
31        if (n <= k) {
32            return 0;
33        } else {
34            // The product of the last 'k' numbers is the last element divided by the (n - k -1)th element.
35            return prefixProducts.get(n - 1) / prefixProducts.get(n - k - 1);
36        }
37    }
38}
39
40// This class can be used as follows:
41// ProductOfNumbers obj = new ProductOfNumbers();
42// obj.add(num);
43// int product = obj.getProduct(k);
44
1#include <vector>
2
3class ProductOfNumbers {
4public:
5    ProductOfNumbers() {
6        // Initialize with 1, to handle the product calculation
7        prefix_products_.push_back(1);
8    }
9
10    void add(int num) {
11        // If number is zero, reset the products list as any subsequent product will be 0
12        if (num == 0) {
13            prefix_products_.clear();
14            prefix_products_.push_back(1);
15        } else {
16            // Otherwise, calculate the new product and add to the list
17            int new_product = prefix_products_.back() * num;
18            prefix_products_.push_back(new_product);
19        }
20    }
21
22    int getProduct(int k) {
23        int size = prefix_products_.size();
24        // If k is greater or equal to the size of the list, return 0 since there are not enough elements
25        if (size <= k) {
26            return 0;
27        } else {
28            // Otherwise, return the product of the last k numbers
29            int product = prefix_products_.back() / prefix_products_[size - k - 1];
30            return product;
31        }
32    }
33
34private:
35    // Stores the prefix products; prefix_products_[i] is the product of all numbers up to index i
36    std::vector<int> prefix_products_;
37};
38
39/**
40 * Your ProductOfNumbers object will be instantiated and called as such:
41 * ProductOfNumbers* obj = new ProductOfNumbers();
42 * obj->add(num);
43 * int param_2 = obj->getProduct(k);
44 */
45
1// A global variable to store the prefix products,
2// where prefixProducts[i] is the product of all numbers up to index i.
3let prefixProducts: number[] = [1];
4
5// Adds a number to the list of products.
6function add(num: number): void {
7    if (num === 0) {
8        // If number is zero, reset the prefixProducts array as any subsequent product will be 0.
9        prefixProducts = [1];
10    } else {
11        // Calculate the new product based on the last element and add it to the prefixProducts array.
12        const newProduct = prefixProducts[prefixProducts.length - 1] * num;
13        prefixProducts.push(newProduct);
14    }
15}
16
17// Returns the product of the last k numbers added.
18function getProduct(k: number): number {
19    const size = prefixProducts.length;
20    if (size <= k) {
21        // If k is greater or equal to the size of the array, return 0 since there are not enough elements.
22        return 0;
23    } else {
24        // Calculate the product of the last k numbers by dividing the last product
25        // by the product at the index 'size - k - 1'.
26        const product = prefixProducts[size - 1] / prefixProducts[size - k - 1];
27        return product;
28    }
29}
30
Not Sure What to Study? Take the 2-min Quiz：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

Time Complexity

  • Initialization (__init__ method): The time complexity is O(1) as it only sets the initial list with one element.

  • Adding a number (add method):

    • If the number is not zero, we multiply the last element in the list by the new number and append the result. This has a time complexity of O(1).
    • If the number is zero, we reset the list which also has a time complexity of O(1).

  • Getting the product (getProduct method):

    • If we need to retrieve the product of the last k numbers, we do so by dividing the last number in the list by the (len(s) - k - 1)th number, given that len(s) is greater than k. The division itself is O(1), but accessing the list elements is also O(1) since list accesses by index in Python are constant time.
    • Returning 0 if len(s) <= k is also O(1).

Overall, for each method, the time complexity is O(1).

Space Complexity

  • The space complexity is primarily due to the list s that stores the product of all numbers up to the current position.

  • Space Complexity for the s list: This grows linearly with the number of elements added, barring when zero resets the list 's'. Therefore, the space complexity is O(n), where n is the number of add operations before the last reset (adding 0).

  • Space Complexity for add and getProduct methods: Aside from the storage in the list s, no additional space is used, so the space complexity for each operation is O(1).

Overall, the space complexity of the ProductOfNumbers class is O(n), where n is the size of the list s at a given time, which equals the number of elements added since the last addition of zero.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Median of Data Stream

Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every

Got a question?Β Ask the Teaching AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

←
↑TA πŸ‘¨β€πŸ«