{x}
blog image

Product of the Last K Numbers

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?

Solution Explanation: Product of the Last K Numbers

This problem requires designing a data structure that efficiently handles adding numbers to a stream and retrieving the product of the last k numbers. A naive approach using a list and iterating for each getProduct call would result in a time complexity of O(k) for getProduct, which is inefficient for large k values. The optimal solution leverages prefix products to achieve O(1) time complexity for both add and getProduct operations.

Approach: Prefix Product Array

The core idea is to maintain a prefix product array. This array, let's call it prefix_products, stores the cumulative product of numbers added to the stream so far. prefix_products[i] will represent the product of all numbers from index 0 up to index i.

  1. Initialization: The prefix_products array is initialized with 1.

  2. add(num):

    • If num is 0, we reset prefix_products to [1] because any product involving 0 will be 0.
    • Otherwise, we append the product of the current last element of prefix_products and num to the array. This efficiently updates the prefix product.

  3. getProduct(k):

    • If the length of prefix_products is less than or equal to k, it means there are not enough numbers in the stream to calculate the product of the last k numbers; we return 0.
    • Otherwise, the product of the last k numbers can be calculated using the prefix products: prefix_products[-1] / prefix_products[-k-1]. This is because prefix_products[-1] contains the product of all numbers up to the current last number and prefix_products[-k-1] contains the product of all numbers up to the k+1th number from the end. Dividing them gives the product of the last k numbers.

Time and Space Complexity Analysis

  • Time Complexity:
    • add(num): O(1) - Constant time operation; appending to the array and multiplication are constant time.
    • getProduct(k): O(1) - Constant time operation; array access and division are constant time.
  • Space Complexity: O(n), where n is the number of numbers added to the stream. This is because we store the prefix products in an array whose size grows with the number of additions.

Code Examples (Python, Java, C++, Go, TypeScript, JavaScript)

The provided code examples in various languages implement this prefix product approach. Each example demonstrates the ProductOfNumbers class with the add and getProduct methods. The comments within the code further explain the logic. Note the handling of the zero case and efficient calculation of the product using prefix product array.