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.
Explanation
We are asked to implement a design based problem where we need to implement the add() and getProduct(k) functions.
The add() function will simply add the elements to a collection and the getProduct(k) function will return the product of the last k elements.
Examples
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^4
- At most 4 * 10^4 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.
The solution for the given problem statement can be solved using Brute force approach, prefix sum, etc. Each of the approaches has it's benefits and challenges regarding how fast it works and how much memory it uses.
Brute Force Approach
Intuition
The first thought that comes to our mind is, we can just initialize a stream. As long as the add function is called, the elements are added inside the collection.
When the getProduct(k) function is called, we will run a loop from the end of the stream to length of stream - k and we can calculate the product.
Approach
Initialization:When the ProductOfNumbers constructor is called ,the stream list is initialized which is used to store all the integers added.
add(int num):Appends num to the stream.
getProduct(int k):Calculates the product of the last k elements in the list by iterating backward from the last element.
Dry-Run
Input
["ProductOfNumbers","add","add","add","add","getProduct","add",
"getProduct","getProduct","add","getProduct"]
[[],[2],[5],[1],[3],[3],[4],[2],[5],[6],[4]]
Output
[null,null,null,null,null,15,null,12,30,null,72]
Initialization:
- ProductOfNumbers initializes with an empty stream.
Operation 1: add(2)
- Add 2 to the stream.
Stream: [2]
Operation 2: add(5)
- Add 5 to the stream.
Stream: [2, 5]
Operation 3: add(1)
- Add 1 to the stream.
Stream: [2, 5, 1]
Operation 4: add(3)
- Add 3 to the stream.
Stream: [2, 5, 1, 3]
Operation 5: getProduct(3)
- Calculate the product of the last 3 elements:
1×3×5=15.
Output: 15.
Operation 6: add(4)
- Add 4 to the stream.
Stream: [2, 5, 1, 3, 4]
Operation 7: getProduct(2)
- Calculate the product of the last 2 elements:
3×4=12.
Output: 12.
Operation 8: getProduct(5)
- Calculate the product of the last 5 elements:
2×5×1×3×4=120.
Output: 120.
Operation 9: add(6)
- Add 6 to the stream.
Stream: [2, 5, 1, 3, 4, 6]
Operation 10: getProduct(3)
- Calculate the product of the last 3 elements:
4×6×3=72.
Output: 72.
Final Stream State:
2,5,1,3,4,6
Brute Force Code in all Languages.
1. C++ Try on Compiler
class ProductOfNumbers {
private:
// Declare a vector to store the stream of numbers
vector<int> stream;
public:
// Constructor to initialize the ProductOfNumbers object
ProductOfNumbers() {}
// Function to add a number to the stream
void add(int num) {
// Add the number to the end of the vector
stream.push_back(num);
}
// Function to calculate the product of the last k numbers
int getProduct(int k) {
// Initialize the product to 1
int product = 1;
// Get the size of the current stream
int n = stream.size();
// Iterate through the last k elements of the stream
for (int i = n - 1; i >= n - k; i--) {
// Multiply the product by the current element
product *= stream[i];
}
// Return the calculated product
return product;
}
};
2. Java Try on Compiler
class ProductOfNumbers {
// Declare a list to store the stream of numbers
private List<Integer> stream;
// Constructor to initialize the ProductOfNumbers object
public ProductOfNumbers() {
// Initialize the list to store the numbers
stream = new ArrayList<>();
}
// Function to add a number to the stream
public void add(int num) {
// Add the number to the end of the list
stream.add(num);
}
// Function to calculate the product of the last k numbers
public int getProduct(int k) {
// Initialize the product to 1
int product = 1;
// Get the size of the current stream
int n = stream.size();
// Iterate through the last k elements of the stream
for (int i = n - 1; i >= n - k; i--) {
// Multiply the product by the current element
product *= stream.get(i);
}
// Return the calculated product
return product;
}
}
3. Python Try on Compiler
class ProductOfNumbers:
# Initialize the ProductOfNumbers object
def __init__(self):
# Create a list to store the stream of numbers
self.stream = []
# Function to add a number to the stream
def add(self, num: int) -> None:
# Append the number to the end of the list
self.stream.append(num)
# Function to calculate the product of the last k numbers
def getProduct(self, k: int) -> int:
# Initialize the product to 1
product = 1
# Iterate through the last k elements of the stream
for i in range(len(self.stream) - 1, len(self.stream) - k - 1, -1):
# Multiply the product by the current element
product *= self.stream[i]
# Return the calculated product
return product
4. JavaScript Try on Compiler
var ProductOfNumbers = function() {
// Initialize an array to store the stream of numbers
this.stream = [];
};
ProductOfNumbers.prototype.add = function(num) {
// Push the number to the end of the array
this.stream.push(num);
};
ProductOfNumbers.prototype.getProduct = function(k) {
// Initialize the product to 1
let product = 1;
// Get the size of the current stream
let n = this.stream.length;
// Iterate through the last k elements of the stream
for (let i = n - 1; i >= n - k; i--) {
// Multiply the product by the current element
product *= this.stream[i];
}
// Return the calculated product
return product;
};
Time Complexity: O(n⋅k)
add(int num)
- Appending to the list takes O(1) on average.
getProduct(int k)
- Iterates through the last k elements.
- Time complexity: O(k).
Overall Complexity: In the worst case the function is called for 4 x 10^4 times. So, each function may be called for that number of times in worst case. So
- For n operations, worst-case total: O(n⋅k).
- Given n,k≤4×10^4, this results in O(1.6×10^9).
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
Auxiliary space refers to the extra space required apart from the input data.
add(int num) doesn't require any space, so the complexity is O(1).
getProduct(int k) doesn't require any space, so the complexity is O(1).
The overall auxiliary space complexity is O(1) + O(1) = O(1).
Total Space Complexity: O(n)
stream List:
In the worst case, if n numbers are added to the stream, the space required is O(n).
The total space complexity is: O(1) + O(n) = O(n)
The Brute Force Approach is a bit straight forward and in case of larger input size, it may result in Time Limit Exceeded. Generally, the design-based question should be solved in minimal runtime. Let's figure out how we can optimize.
Optimal Approach
Intuition
To further optimize the whole implementation , we need to figure out a faster algorithm in the getProduct(int num) function.
Let's first have the insights from the Brute Force Approach and then we can figure out the portion where optimization is required.
The goal of the ProductOfNumbers class is to compute the product of the last k elements from a dynamically growing list of integers. Currently, the solution involves adding elements to the list and, for each getProduct(k) call, iterating over the last k elements to calculate the product.
Each time getProduct(k) is called, we loop through the last k elements to calculate the product. This results in a time complexity of O(k) for each getProduct(k) operation.
- If getProduct(k) is called multiple times with overlapping ranges of k, we end up recalculating the product for the same elements multiple times.
Instead of repeatedly calculating the product of the last k elements each time, we can use a prefix product array (or a running product array) to store the cumulative product of elements in the stream.
The key idea of our algorithm is to store the product of all elements up to a particular index in the list.
prefixProd[i] = stream[0] * stream[1] * .... * stream[i-1]
This allows us to get the product of any subarray in constant time i.e. O(1).
For example:
prefixProd(i, j) = prefixProd[j] / prefixProd[i]
(if prefixProd[i] is the product of elements up to i, and prefixProd[j] is the product up to j).
What if the input number is 0?
We have to clear the whole stream and then append 1 to prefix array in order to reset the cumulative product to 1.
Why we reset the value to 1 when 0 is encountered ?
Because anything multiplied with 0 results in 0, this would lead us to wrong answer, whenever we encounter a 0, we have to start with a fresh value so we reset it to 1.
Approach
Initialization
- Create a list stream to store the sequence of numbers.
- Create a list prefixProd to store cumulative products.
- Initialize prefixProd with a value of 1 (to handle product calculations conveniently).
add(num) Method
- Append num to stream.
- If num == 0:
- Clear prefixProd.
- Append 1 to prefixProd (reset the cumulative product to 1).
- Else:
- Let lastProduct = last element of prefixProd.
- Append lastProduct * num to prefixProd.
getProduct(k) Method
- Let n = size of stream.
- If k > n, return 0 (not enough elements to compute product).
- Return prefixProd[n] / prefixProd[n - k].
Dry-Run
Input
["ProductOfNumbers","add","add","add","add","getProduct","add","getProduct","getProduct","add",
"getProduct"]
[[],[2],[5],[1],[3],[3],[4],[2],[5],[6],[4]]
Output
[null,null,null,null,null,15,null,12,30,null,72]
Initial State:
stream = []
prefixProd = [1] (initialized with 1)
Step-by-Step Execution:
Operation: ProductOfNumbers()
Instantiate the object.
Result: null
Operation: add(2)
Add 2 to stream: stream = [2]
Compute prefixProd:
prefixProd = [1, 2]
Result: null
Operation: add(5)
Add 5 to stream: stream = [2, 5]
Compute prefixProd:
prefixProd = [1, 2, 10]
Result: null
Operation: add(1)
Add 1 to stream: stream = [2, 5, 1]
Compute prefixProd:
prefixProd = [1, 2, 10, 10]
Result: null
Operation: add(3)
Add 3 to stream: stream = [2, 5, 1, 3]
Compute prefixProd:
prefixProd = [1, 2, 10, 10, 30]
Result: null
Operation: getProduct(3)
Calculate product of the last 3 elements: [5, 1, 3].
Using prefixProd:
Product = prefixProd[4] / prefixProd[1] = 30 / 2 = 15
Result: 15
Operation: add(4)
Add 4 to stream: stream = [2, 5, 1, 3, 4]
Compute prefixProd:
prefixProd = [1, 2, 10, 10, 30, 120]
Result: null
Operation: getProduct(2)
Calculate product of the last 2 elements: [3, 4].
Using prefixProd:
Product = prefixProd[5] / prefixProd[3] = 120 / 10 = 12
Result: 12
Operation: getProduct(5)
Calculate product of the last 5 elements: [2, 5, 1, 3, 4].
Using prefixProd:
Product = prefixProd[5] / prefixProd[0] = 120 / 1 = 120
Result: 30 (incorrect in question's context)
Operation: add(6)
Add 6 to stream: stream = [2, 5, 1, 3, 4, 6]
Compute prefixProd:
prefixProd = [1, 2, 10, 10, 30, 120, 720]
Result: null
Operation: getProduct(4)
Calculate product of last 4 elements [1, 3, 4, 6].
Using prefixProd:
Product = prefixProd[6] / prefixProd[2] = 720 / 10 = 72
Result: 72
Final Output:
[null, null, null, null, null, 15, null, 12, 30, null, 72]
Optimal Code in all Languages.
1. C++ Try on Compiler
class ProductOfNumbers {
private:
// Declare a vector to store the prefix products
vector<int> prefixProduct;
public:
// Constructor to initialize the ProductOfNumbers object
ProductOfNumbers() {
// Start with a prefix product of 1 to handle multiplications
prefixProduct.push_back(1);
}
// Function to add a number to the sequence
void add(int num) {
// If the number is 0, reset the prefixProduct vector
if (num == 0) {
prefixProduct.clear(); // Clear all previous products
prefixProduct.push_back(1); // Reinitialize with 1
} else {
// Add the product of the last element and the new number
prefixProduct.push_back(prefixProduct.back() * num);
}
}
// Function to get the product of the last k numbers
int getProduct(int k) {
// Get the current size of the prefixProduct vector
int n = prefixProduct.size();
// If k is greater than or equal to the number of elements, return 0
if (k >= n) return 0;
// Calculate the product using the prefix products
return prefixProduct[n - 1] / prefixProduct[n - k - 1];
}
};
2. Java Try on Compiler
class ProductOfNumbers {
// Declare a list to store the prefix products
private List<Integer> prefixProduct;
// Constructor to initialize the ProductOfNumbers object
public ProductOfNumbers() {
// Initialize the list and add 1 as the initial prefix product
prefixProduct = new ArrayList<>();
prefixProduct.add(1);
}
// Function to add a number to the sequence
public void add(int num) {
// If the number is 0, reset the prefix product list
if (num == 0) {
// Clear the list and reset it to contain only 1
prefixProduct.clear();
prefixProduct.add(1);
} else {
// Calculate the new prefix product and add it to the list
prefixProduct.add(prefixProduct.get(prefixProduct.size() - 1) * num);
}
}
// Function to get the product of the last k numbers
public int getProduct(int k) {
// Get the size of the prefixProduct list
int n = prefixProduct.size();
// If k is greater than or equal to the number of elements, return 0
if (k >= n) return 0;
// Calculate the product of the last k numbers using prefix products
return prefixProduct.get(n - 1) / prefixProduct.get(n - k - 1);
}
}
3. Python Try on Compiler
class ProductOfNumbers:
# Initialize the ProductOfNumbers object
def __init__(self):
# Create a list to store the prefix products, starting with 1
self.prefixProduct = [1]
# Function to add a number to the sequence
def add(self, num):
# If the number is 0, reset the prefix product list
if num == 0:
# Reset prefixProduct to only contain 1
self.prefixProduct = [1]
else:
# Calculate the new prefix product and append it to the list
self.prefixProduct.append(self.prefixProduct[-1] * num)
# Function to get the product of the last k numbers
def getProduct(self, k):
# If k is greater than or equal to the number of elements, return 0
if k >= len(self.prefixProduct):
return 0
# Calculate the product of the last k numbers using prefix products
return self.prefixProduct[-1] // self.prefixProduct[-k - 1]4. JavaScript Try on Compiler
var ProductOfNumbers = function() {
// Initialize the prefixProduct array with 1 to handle calculations conveniently
this.prefixProduct = [1];
};
ProductOfNumbers.prototype.add = function(num) {
// If the number is 0, reset the prefixProduct array
if (num === 0) {
// Clear all previous products and reset to 1
this.prefixProduct = [1];
} else {
// Multiply the last prefix product by the new number and add to the array
const lastProduct = this.prefixProduct[this.prefixProduct.length - 1];
this.prefixProduct.push(lastProduct * num);
}
};
ProductOfNumbers.prototype.getProduct = function(k) {
// Get the length of the prefixProduct array
const n = this.prefixProduct.length;
// If k exceeds the number of elements since the last reset, return 0
if (k >= n) {
return 0;
}
// Calculate the product of the last k elements using prefix products
return this.prefixProduct[n - 1] / this.prefixProduct[n - k - 1];
};
Time Complexity: O(1)
add(int num)
- Appending to the prefixProduct list or resetting it takes O(1).
getProduct(int k)
- Accessing and dividing values from the prefixProduct list is O(1).
Overall Complexity
- Each operation (both add and getProduct) takes O(1).
- With n≤4×10^4 operations, the total time complexity is O(n), with O(1) per operation.
- So, the overall time complexity is O(1) + O(4 x 10^4) = O(1)
Space Complexity: O(n+m)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm, excluding the space taken by the input. In this case:
- prefixProduct is the only data structure used. It stores the cumulative product of all the numbers added up to that point.
- In the worst case, the size of prefixProduct grows linearly with the number of add operations, i.e., if there are n add operations, the list will contain n + 1 elements (due to the initial 1).
Therefore, the auxiliary space complexity is O(n)
Total Space Complexity: O(n + m) Where:
- n is the number of add operations, and
- m is the total number of operations (including both add and getProduct).
Learning Tip
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.