Leetcode 1352. Product of the Last K Numbers

Problem Explanation

The problem is about implementing a class called ProductOfNumbers that supports two methods. The first method is add, which is used to add numbers to the end of a list. The second method is getProduct that returns the product of the last k numbers in the list. At any given time, the product of any contiguous sequence of numbers will not overflow a 32-bit integer.

Let's understand the problem by walking through an example:

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

In the example above, there were two operations, adding the numbers and getting the product of the last k numbers. The operations are carried out in sequence, and the result is recorded.

Solution Approach

The approach for this problem uses the concept of prefix product. In this concept we keep track of the running product of all elements. The main advantage of storing the prefix product is that it allows constant time retrieval of the product of any given number of last elements. We start with prefix[0] = 1 (This will handle the case when fetching product of zero numbers).

The solution approach is simple.

• For adding a new number, we append the product of new number and the last product in prefix array.
• For fetching product, if the number of elements (k) is more than size of prefix, we return 0, because multiplying by 0. If not we return the prefix of the last number divided by prefix of the number prefix.size() - k - 1.

This approach facilitates the fetching of product in constant time.

Consider the following example: prefix = {1}, add(3), prefix => {1, 3}, getProduct(1) => prefix[2]/prefix[2 - 1 - 1] = 3

Python Solution

1
2python
3class ProductOfNumbers:
4    def __init__(self):
5        self.prefix = [1]
6
7    def add(self, num):
8        if num == 0:
9            self.prefix = [1]
10        else:
11            self.prefix.append(self.prefix[-1] * num)
12
13    def getProduct(self, k):
14        if k >= len(self.prefix):
15            return 0
16        else:
17            return self.prefix[-1] // self.prefix[-k-1] if k < len(self.prefix) else 0

Java Solution

1
2java
3class ProductOfNumbers {
4  private List<Integer> prefix = new ArrayList<>();
5
6  public ProductOfNumbers() {
7    prefix.add(1);
8  }
9
10  public void add(int num) {
11    if (num > 0)
12      prefix.add(prefix.get(prefix.size() - 1) * num);
13    else 
14      prefix = new ArrayList<>();
15      prefix.add(1);
16  }
17
18  public int getProduct(int k) {
19    int n = prefix.size();
20    return k < n ? prefix.get(n - 1) / prefix.get(n - k - 1) : 0;
21  }
22}

JavaScript Solution

1
2javascript
3class ProductOfNumbers {
4  constructor() {
5    this.prefix = [1];
6  }
7
8  add(num) {
9    if (num === 0) {
10      this.prefix = [1];
11    } else {
12      this.prefix.push(this.prefix[this.prefix.length - 1] * num);
13    }
14  }
15
16  getProduct(k) {
17    if (k >= this.prefix.length) {
18      return 0;
19    } else {
20      return this.prefix[this.prefix.length - 1] / this.prefix[this.prefix.length - k - 1];
21    }
22  }
23}

C++ Solution

1
2cpp
3class ProductOfNumbers {
4    vector<int> prefix;
5public:
6    ProductOfNumbers() {
7        prefix={1};
8    }
9    
10    void add(int num) {
11        if(num == 0)
12            prefix = {1};
13        else
14            prefix.push_back(prefix.back()*num);
15    }
16    
17    int getProduct(int k) {
18        if(k >= prefix.size()) 
19            return 0;
20       else
21            return prefix.back()/prefix[prefix.size() - k - 1];
22    }
23};

C# Solution

1
2cs
3public class ProductOfNumbers {
4    List<int> prefix = new List<int>(){1};
5    
6    public ProductOfNumbers() {
7        
8    }
9    
10    public void Add(int num) {
11        if (num == 0)
12            this.prefix = new List<int>(){1}; 
13        else 
14            this.prefix.Add(this.prefix[this.prefix.Count - 1] * num); 
15    }
16    
17    public int GetProduct(int k) {
18        return k < this.prefix.Count ? this.prefix[this.prefix.Count - 1] / this.prefix[this.prefix.Count - k - 1] : 0;
19    }
20}

To elaborate on the approach, the solutions provided use a clever mechanism of storing prefix products, which keeps track of the running product as you add numbers to the structure. Whenever a zero is encountered, the prefix array reverts to [1] as multiplying anything with zero gives you zero. This clears previous computations due to the rule of getting the last k numbers in multiplication - any multiplication sequence with a zero will result in a zero.

When you call getProduct(int k), if k is equal or greater than the length of the prefix array, it means the sequence involves multiplication with zero hence it returns zero. Otherwise, it finds the prefix product upon the addition of a new number.

Since the approach maintains a running product of the numbers, it allows efficient and constant time retrieval of the product of any given number of last elements.

Let's highlight few properties of this solution:

• Space Complexity: The solution has a space complexity of O(n) because of the extra space used to store prefix product.
• Time Complexity: The time complexity for both add and getProduct operations is O(1). This is because adding an element just involves multiplying the last element in prefix list (constant time operation) and getting product involves a simple division.

In conclusion, the solution using prefix product array is an efficient way to handle this problem as it supports both adding a number and getting the product of last k numbers in constant time. This approach can further be useful in more complex array-related problems where prefix sums or products are frequently required.