1352. Product of the Last K Numbers

Intuition

Maintain a running product with a pointer. Use a deque or array storing products. getProduct(k) = total_product / product_before_last_k.

Algorithm

1Store prefix products. When adding: multiply into running product. For getProduct(k): return product of last k = prefix[-1] / prefix[-1-k].
2Handle zeros: reset running product on zero.

Common Pitfalls

•Division by zero when list contains 0. Track index of last zero; if within last k, product is 0.

1352.cs

// Approach: Running prefix product; reset on 0; GetProduct(k) = prefix.last / prefix[n-k] or 0 if a zero is within the window.
// Time: O(1) per op Space: O(n)

public class ProductOfNumbers
{
    private List<int> prefix;
    public ProductOfNumbers()
    {
        prefix = new List<int> { 1 };
    }

    public void Add(int num)
    {
        if (num == 0)
            prefix = new List<int> { 1 };
        else
            prefix.Add(prefix[prefix.Count - 1] * num);
    }

    public int GetProduct(int k)
    {
        return k >= prefix.Count ? 0 : prefix[prefix.Count - 1] / prefix[prefix.Count - 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);
 */

Was this solution helpful?