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

Math Design Data Stream Prefix Sum

Data structures

Array

Companies

Tekion Target

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 * 10⁴
At most 4 * 10⁴ 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.

1import java.util.ArrayList;2import java.util.List;3 4class ProductOfNumbers {5    List<Integer> stream;6 7    public ProductOfNumbers() {8        stream = new ArrayList<>();9    }10    11    public void add(int num) {12        stream.add(num);13    }14    15    public int getProduct(int k) {16        int product = 1;17        int n = stream.size();18        for (int i = n - k; i < n; i++) {19            product *= stream.get(i);20        }21        return product;22    }23}

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.

To achieve constant time for both add and getProduct, we can use a prefix product technique. We maintain a list of cumulative products. The product of a sub-array can be found in O(1) by dividing two prefix products. The main challenge is handling zeros, which act as a reset point for the product calculations.

Algorithm

Initialize a list prefixProducts with a single element, 1.
add(int num) method:
- If num is 0, it means any product including this number will be zero. We reset the stream by re-initializing prefixProducts to a new list containing just 1.
- If num is greater than 0, we get the last prefix product from the list, multiply it by num, and append the new result to prefixProducts.
getProduct(int k) method:
- Get the current size of prefixProducts, n.
- If k is greater than or equal to n, it implies that the original last k numbers must have included a 0 (which caused our list to reset and be shorter than k+1). Thus, the product is 0.
- Otherwise, the product of the last k numbers is (product of all numbers since last zero) / (product of numbers before the last k). This translates to prefixProducts.get(n - 1) / prefixProducts.get(n - 1 - k).

Walkthrough

This optimized approach leverages prefix products to answer getProduct(k) queries in constant time. The key insight is that the product of elements from index i to j is equal to prefix_product[j] / prefix_product[i-1].

A zero in the stream complicates this, as prefix_product would become zero for all subsequent elements, leading to division by zero issues. We handle this by treating a zero as a reset signal. Whenever a 0 is added, we start a new list of prefix products.

Our data structure is a list, prefixProducts, initialized with 1. This initial 1 serves as a sentinel value to simplify calculations.

add(int num): If num is 0, we discard the current prefixProducts list and start a new one with [1]. If num > 0, we append last_product * num to the list. This is an O(1) operation.
getProduct(int k): Let the size of prefixProducts be n. If k >= n, it means the desired range of k numbers extends back to or before the last 0, so the product is 0. Otherwise, the product of the last k numbers is the division of the last prefix product by the prefix product at index n - 1 - k. This is an O(1) operation.

1import java.util.ArrayList;2import java.util.List;3 4class ProductOfNumbers {5    List<Integer> prefixProducts;6 7    public ProductOfNumbers() {8        // Initialize with 1 to handle division and edge cases.9        prefixProducts = new ArrayList<>();10        prefixProducts.add(1);11    }12    13    public void add(int num) {14        if (num == 0) {15            // If a zero is added, it resets the product stream.16            prefixProducts = new ArrayList<>();17            prefixProducts.add(1);18        } else {19            // Append the new cumulative product.20            int lastProduct = prefixProducts.get(prefixProducts.size() - 1);21            prefixProducts.add(lastProduct * num);22        }23    }24    25    public int getProduct(int k) {26        int n = prefixProducts.size();27        28        // If k is larger than or equal to the current list size, it means29        // a zero must be in the last k numbers of the original stream.30        if (k >= n) {31            return 0;32        }33        34        // The product of the last k numbers is P[n-1] / P[n-1-k]35        int totalProduct = prefixProducts.get(n - 1);36        int prevProduct = prefixProducts.get(n - 1 - k);37        return totalProduct / prevProduct;38    }39}

Complexity

Time

- `add(num)`: O(1) amortized time. - `getProduct(k)`: O(1) time.

Space

O(M), where M is the number of elements added since the last `0`. In the worst-case scenario (no zeros), the space complexity is O(N), where N is the total number of `add` calls.

Trade-offs

Pros

Extremely efficient, with both add and getProduct operations running in O(1) time.
Meets the requirements of the follow-up question.

Cons

The logic is more complex due to the special handling required for zeros.
Space complexity is still linear in the number of elements added since the last zero.

Solutions

Solution

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

1class ProductOfNumbers { s = [ 1 ]; add ( num ) { if ( num === 0 ) { this . s = [ 1 ]; } else { const i = this . s . length ; this . s [ i ] = this . s [ i - 1 ] * num ; } } getProduct ( k ) { const i = this . s . length ; if ( k > i - 1 ) return 0 ; return this . s [ i - 1 ] / this . s [ i - k - 1 ]; } }

1class ProductOfNumbers { public: ProductOfNumbers () { s . push_back ( 1 ); } void add ( int num ) { if ( num == 0 ) { s . clear (); s . push_back ( 1 ); return ; } s . push_back ( s . back () * num ); } int getProduct ( int k ) { int n = s . size (); return n <= k ? 0 : s . back () / s [ n - k - 1 ]; } private: vector < int > s ; }; /** * Your ProductOfNumbers object will be instantiated and called as such: * ProductOfNumbers* obj = new ProductOfNumbers(); * obj->add(num); * int param_2 = obj->getProduct(k); */

1class ProductOfNumbers : def __init__ ( self ): self . s = [ 1 ] def add ( self , num : int ) -> None : if num == 0 : self . s = [ 1 ] return self . s . append ( self . s [ - 1 ] * num ) def getProduct ( self , k : int ) -> int : return 0 if len ( self . s ) <= k else self . s [ - 1 ] // self . s [ - k - 1 ] # Your ProductOfNumbers object will be instantiated and called as such: # obj = ProductOfNumbers() # obj.add(num) # 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 problem