✅ Easy Explanation | Prefix Sum | Beats 100% | Detailed Video Explanation🔥
IntuitionThe problem requires efficiently computing the product of the last k numbers in a dynamic stream of integers.
A naive approach would involve maintainin
# Intuition
The problem requires efficiently computing the product of the last `k` numbers in a dynamic stream of integers.  
A naive approach would involve maintaining the entire list and recalculating the product each time, leading to `O(k)` complexity per query.  
To optimize this, we can leverage prefix products, which allow us to compute the result in constant time.

# Approach
1. **Maintain a prefix product list**:
   - Store the cumulative product of all numbers added so far.
   - If a zero is encountered, reset the list since any product involving zero would be zero.
   
2. **Adding a number** (`add(num)`):
   - If `num == 0`, reset the prefix list to discard previous values.
   - Otherwise, multiply the last stored product with `num` and store it in the list.

3. **Fetching the product of the last `k` numbers** (`getProduct(k)`):
   - If `k > size of prefix list`, return `0` (as a zero must have been encountered).
   - If `k == size`, return the last stored product.
   - Otherwise, divide the last stored product by the prefix product at index `(size - k - 1)` to get the result efficiently in `O(1)` time.

# Complexity
- **Time complexity**:
  - `add(num)`: $$O(1)$$ (constant time insertion and multiplication)
  - `getProduct(k)`: $$O(1)$$ (constant time lookup and division)

- **Space complexity**:
  - $$O(n)$$ where `n` is the number of elements stored in the prefix list.

This approach ensures an efficient solution without recalculating products for every query.


# Code
```java []
// Asked in Meta, Google, Amazon, Apple, TikTok
class ProductOfNumbers {
    // Stores the prefix product of numbers
    List<Integer> prefix;

    public ProductOfNumbers() {
        prefix = new ArrayList<>();
    }

    // Adds a number to the sequence
    // Time Complexity: O(1)
    public void add(int num) {
        if (num == 0) { 
            // Reset the prefix product list when encountering zero
            // Since any product involving zero is zero, we need to discard previous values
            prefix = new ArrayList<>();
        } else if (prefix.size() == 0) {  
            // If it's the first number, simply add it
            prefix.add(num);
        } else {
            // Store the cumulative product
            prefix.add(num * prefix.get(prefix.size() - 1));
        }
    }

    // Returns the product of the last k numbers
    // Time Complexity: O(1)
    public int getProduct(int k) {
        int n = prefix.size();
        if (k > n) return 0;  // If k is larger than available numbers, return 0
        if (k == n) return prefix.get(n - 1);  // If k equals the size, return the last product

        // Otherwise, use the prefix array to compute the product in constant time
        return prefix.get(n - 1) / prefix.get(n - 1 - k);
    }
}

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers obj = new ProductOfNumbers();
 * obj.add(num);
 * int param_2 = obj.getProduct(k);
 */

```

https://youtu.be/F0anehzE88Y


['Array', 'Design', 'Data Stream', 'Prefix Sum', 'Java']