LeetCode 1352. Product of the Last K Numbers

, , ,

Question

Implement the class ProductOfNumbers that supports two methods:

1. add(int num)

  • Adds the number num to the back of the current list of numbers.

2. 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.

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

Solution

We use the approach like prefix sum, and be careful of zero, when we get the zero, we clear the whole array, becasue after that, all the product would be zero. However, when it comes non-zero number, we have to add to the list as usual and when we have to get the last K product, we need compare the size.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// time:O(1) space:O(n)
    List<Integer> list;
    
    public ProductOfNumbers() {
        add(0);
    }
    
    public void add(int num) {
        if (num > 0) {
            list.add(list.get(list.size() - 1) * num);
        } else {
            list = new ArrayList<>();
            list.add(1);
        }
    }
    
    public int getProduct(int k) {
        int n = list.size();
        return k < n ? (list.get(n - 1) / list.get(n - 1 - k)) : 0;
    }

Reference