# Product of the Last K Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/product-of-the-last-k-numbers)
Canonical: https://scaleengineer.com/dsa/problems/product-of-the-last-k-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Tekion](https://scaleengineer.com/companies/tekion), [Target](https://scaleengineer.com/companies/target)
---
## Problem
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 * 104`
* At most `4 * 104` 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?

# Approaches
## Brute Force Approach
This straightforward approach involves storing all the numbers from the stream in a list. When the product of the last `k` numbers is requested, we simply iterate through the last `k` elements of this list and compute their product on the fly.
**Time:** - `add(num)`: O(1) amortized time.
- `getProduct(k)`: O(k) time, as it requires iterating through `k` elements. · **Space:** O(N), where N is the total number of elements added to the stream. We need to store every number.
**Pros:** Very simple to understand and implement.; Requires minimal logic and is less prone to bugs.
**Cons:** The `getProduct(k)` operation has a time complexity of O(k), which can be slow if `k` is large and `getProduct` is called frequently.
### Explanation
In this approach, we use a dynamic array (like `ArrayList` in Java) to maintain the sequence of numbers added. 

- The `add(num)` operation is very simple: we just append the new number to our list. This is an amortized constant time operation, O(1).

- The `getProduct(k)` operation requires us to calculate the product of the last `k` elements. We can do this by accessing the last `k` elements from our list. We find the starting index, which is `list.size() - k`, and iterate up to the end of the list, multiplying the numbers together. This process takes time proportional to `k`, making its time complexity O(k).

This method is easy to implement and correctly handles all cases, including when a `0` is part of the last `k` numbers, as multiplying by `0` will naturally result in a product of `0`.

```java
import java.util.ArrayList;
import java.util.List;

class ProductOfNumbers {
    List<Integer> stream;

    public ProductOfNumbers() {
        stream = new ArrayList<>();
    }
    
    public void add(int num) {
        stream.add(num);
    }
    
    public int getProduct(int k) {
        int product = 1;
        int n = stream.size();
        for (int i = n - k; i < n; i++) {
            product *= stream.get(i);
        }
        return product;
    }
}
```
### Algorithm
- Initialize a dynamic list, let's call it `stream`, in the constructor.
- **`add(int num)` method:**
  - Simply append the given `num` to the end of the `stream` list.
- **`getProduct(int k)` method:**
  - Initialize a variable `product` to 1.
  - Get the current size of the list, `n`.
  - Iterate from the index `n - k` to `n - 1`.
  - In each step of the loop, multiply the current `product` by the element at the current index in `stream`.
  - After the loop finishes, return the final `product`.

## Optimized Approach using Prefix Products
To achieve constant time for both `add` and `getProduct`, we can use a prefix product technique. We maintain a list of cumulative products. The product of a sub-array can be found in O(1) by dividing two prefix products. The main challenge is handling zeros, which act as a reset point for the product calculations.
**Time:** - `add(num)`: O(1) amortized time.
- `getProduct(k)`: O(1) time. · **Space:** O(M), where M is the number of elements added since the last `0`. In the worst-case scenario (no zeros), the space complexity is O(N), where N is the total number of `add` calls.
**Pros:** Extremely efficient, with both `add` and `getProduct` operations running in O(1) time.; Meets the requirements of the follow-up question.
**Cons:** The logic is more complex due to the special handling required for zeros.; Space complexity is still linear in the number of elements added since the last zero.
### Explanation
This optimized approach leverages prefix products to answer `getProduct(k)` queries in constant time. The key insight is that the product of elements from index `i` to `j` is equal to `prefix_product[j] / prefix_product[i-1]`.

A zero in the stream complicates this, as `prefix_product` would become zero for all subsequent elements, leading to division by zero issues. We handle this by treating a zero as a reset signal. Whenever a `0` is added, we start a new list of prefix products. 

Our data structure is a list, `prefixProducts`, initialized with `1`. This initial `1` serves as a sentinel value to simplify calculations.

- **`add(int num)`:** If `num` is `0`, we discard the current `prefixProducts` list and start a new one with `[1]`. If `num > 0`, we append `last_product * num` to the list. This is an O(1) operation.

- **`getProduct(int k)`:** Let the size of `prefixProducts` be `n`. If `k >= n`, it means the desired range of `k` numbers extends back to or before the last `0`, so the product is `0`. Otherwise, the product of the last `k` numbers is the division of the last prefix product by the prefix product at index `n - 1 - k`. This is an O(1) operation.

```java
import java.util.ArrayList;
import java.util.List;

class ProductOfNumbers {
    List<Integer> prefixProducts;

    public ProductOfNumbers() {
        // Initialize with 1 to handle division and edge cases.
        prefixProducts = new ArrayList<>();
        prefixProducts.add(1);
    }
    
    public void add(int num) {
        if (num == 0) {
            // If a zero is added, it resets the product stream.
            prefixProducts = new ArrayList<>();
            prefixProducts.add(1);
        } else {
            // Append the new cumulative product.
            int lastProduct = prefixProducts.get(prefixProducts.size() - 1);
            prefixProducts.add(lastProduct * num);
        }
    }
    
    public int getProduct(int k) {
        int n = prefixProducts.size();
        
        // If k is larger than or equal to the current list size, it means
        // a zero must be in the last k numbers of the original stream.
        if (k >= n) {
            return 0;
        }
        
        // The product of the last k numbers is P[n-1] / P[n-1-k]
        int totalProduct = prefixProducts.get(n - 1);
        int prevProduct = prefixProducts.get(n - 1 - k);
        return totalProduct / prevProduct;
    }
}
```
### Algorithm
- Initialize a list `prefixProducts` with a single element, `1`.
- **`add(int num)` method:**
  - If `num` is `0`, it means any product including this number will be zero. We reset the stream by re-initializing `prefixProducts` to a new list containing just `1`.
  - If `num` is greater than `0`, we get the last prefix product from the list, multiply it by `num`, and append the new result to `prefixProducts`.
- **`getProduct(int k)` method:**
  - Get the current size of `prefixProducts`, `n`.
  - If `k` is greater than or equal to `n`, it implies that the original last `k` numbers must have included a `0` (which caused our list to reset and be shorter than `k+1`). Thus, the product is `0`.
  - Otherwise, the product of the last `k` numbers is `(product of all numbers since last zero) / (product of numbers before the last k)`. This translates to `prefixProducts.get(n - 1) / prefixProducts.get(n - 1 - k)`.

# Solutions
### Java

```java
class ProductOfNumbers { private List < Integer > s = new ArrayList <>(); public ProductOfNumbers () { s . add ( 1 ); } public void add ( int num ) { if ( num == 0 ) { s . clear (); s . add ( 1 ); return ; } s . add ( s . get ( s . size () - 1 ) * num ); } public int getProduct ( int k ) { int n = s . size (); return n <= k ? 0 : s . get ( n - 1 ) / s . get ( n - 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); */
```

### JavaScript

```javascript
class ProductOfNumbers { s = [ 1 ]; add ( num ) { if ( num === 0 ) { this . s = [ 1 ]; } else { const i = this . s . length ; this . s [ i ] = this . s [ i - 1 ] * num ; } } getProduct ( k ) { const i = this . s . length ; if ( k > i - 1 ) return 0 ; return this . s [ i - 1 ] / this . s [ i - k - 1 ]; } }
```

### CPP

```cpp
class ProductOfNumbers { public: ProductOfNumbers () { s . push_back ( 1 ); } void add ( int num ) { if ( num == 0 ) { s . clear (); s . push_back ( 1 ); return ; } s . push_back ( s . back () * num ); } int getProduct ( int k ) { int n = s . size (); return n <= k ? 0 : s . back () / s [ n - k - 1 ]; } private: vector < int > s ; }; /** * Your ProductOfNumbers object will be instantiated and called as such: * ProductOfNumbers* obj = new ProductOfNumbers(); * obj->add(num); * int param_2 = obj->getProduct(k); */
```

### Python

```python
class ProductOfNumbers : def __init__ ( self ): self . s = [ 1 ] def add ( self , num : int ) -> None : if num == 0 : self . s = [ 1 ] return self . s . append ( self . s [ - 1 ] * num ) def getProduct ( self , k : int ) -> int : return 0 if len ( self . s ) <= k else self . s [ - 1 ] // self . s [ - k - 1 ] # Your ProductOfNumbers object will be instantiated and called as such: # obj = ProductOfNumbers() # obj.add(num) # param_2 = obj.getProduct(k)
```