**"Optimized Prefix Product with Zero Handling – O(1) Query | Java | 15ms 🔥 Beats 91.34%"** 🚀
IntuitionThe problem requires designing a data structure that maintains a stream of integers and efficiently retrieves the product of the last k elements. A nai
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires designing a data structure that maintains a stream of integers and efficiently retrieves the product of the last k elements. A naive approach would be to store all elements and compute the product on demand, leading to an O(k) complexity per query. However, we can optimize this by maintaining a prefix product array.

# Approach
<!-- Describe your approach to solving the problem. -->
Maintain a prefix product list (a):

If a new number is not zero, append the product of the last stored value and the new number.
If a new number is zero, reset the prefix product list and store its index (idx).

Handling zero efficiently:
If a 0 is added, all previous products become irrelevant because any product containing 0 is 0.
Track the last index of 0 (idx) to determine if a valid k-length product is possible.
Querying the product efficiently:

If idx (index of last zero) is within the last k elements, return 0.
Otherwise, use prefix division:
If k == size of the list, return a[s-1] directly.
Otherwise, return a[s-1] / a[s-k-1].

    ProductOfNumbers obj = new ProductOfNumbers();
    obj.add(3);  // [3]
    obj.add(2);  // [3, 6]   (prefix product)
    obj.add(5);  // [3, 6, 30]
    obj.getProduct(2);  // returns 10 (last 2 numbers: 2 * 5)
    obj.add(0);  // [3, 6, 30, 0] (reset due to zero)
    obj.add(4);  // [3, 6, 30, 0, 4] (start new sequence)
    obj.add(2);  // [3, 6, 30, 0, 4, 8]
    obj.getProduct(2);  // returns 8 (last 2 numbers: 4 * 2)
    obj.getProduct(4);  // returns 0 (zero within last 4 numbers)

**Step-by-Step Execution :**
Step 1: add(3)

    Prefix product list: [3]

Step 2: add(2)

    Multiply last element 3 by 2 → 6
    Prefix product list: [3, 6]
Step 3: add(5)

    Multiply last element 6 by 5 → 30
    Prefix product list: [3, 6, 30]
Step 4: getProduct(2)

    Last 2 elements: 2, 5
    Product: 30 / 3 = 10
    Returns: 10
Step 5: add(0)

    Reset due to 0
    Prefix product list: [3, 6, 30, 0]
    Index of last zero (idx): 3

Step 6: add(4)

    Prefix product list: [3, 6, 30, 0, 4]

Step 7: add(2)

    Multiply last element 4 by 2 → 8
    Prefix product list: [3, 6, 30, 0, 4, 8]
Step 8: getProduct(2)

    Last 2 elements: 4, 2
    Product: 8 / 4 = 8
    Returns: 8
Step 9: getProduct(4)

    Last 4 elements: 0, 4, 2
    Since a 0 is within the last 4 elements, return 0
    Returns: 0



# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
        add(num): O(1) (appends and multiplies values)
        getProduct(k): O(1) (performs at most one division)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
        O(n) (stores prefix product values)


# Code
```java []
class ProductOfNumbers {
    ArrayList<Integer> a;
    int idx;
    public ProductOfNumbers() {
        a = new ArrayList<>();
        idx = Integer.MIN_VALUE;
    }
    
    public void add(int num) {
        if(num != 0 )
        {
            int s = a.size();
            if(s == 0)
                a.add(num);
            else{
                int x = a.get(s - 1);
                if(x != 0)
                    a.add(x * num);
                else
                    a.add(num);
            }
        }
        else
        {
            a.add(num);
            idx = a.size() - 1;
        }
    }
    
    public int getProduct(int k) {
        int s = a.size();
        int l = a.get(s - 1);
        if(idx >= s - k)
            return 0;
        if(k == s || a.get(s - k -1) == 0)
            return l;
        return l / a.get(s - k -1);
    }
}
![upvote.png](https://assets.leetcode.com/users/images/8d479089-37c5-4ed6-9635-4002fc5f8fe6_1739532977.7929008.png)


/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers obj = new ProductOfNumbers();
 * obj.add(num);
 * int param_2 = obj.getProduct(k);
 */
```
['Prefix Sum', 'Java']