Scale Engineer

Product of the Last K Numbers

Med
#1255Time: - `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.2 companies
Patterns
MathDesignData StreamPrefix Sum
Data structures
Array
Companies
TekionTarget

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem