The "Product of the Last K Numbers" problem requires you to design a class that supports two types of operations:
add(num): Adds the integer num to the end of a list.
getProduct(k): Returns the product of the last k numbers in the current list.
If any of the last k numbers is zero, the product should be zero. The operations are called multiple times and need to be efficient.
Constraints:
add and getProduct.getProduct, which should not recompute products from scratch each time.
The first idea that comes to mind is to store all the numbers in a list and, whenever getProduct(k) is called, multiply the last k numbers together. While this works for small inputs, it becomes very slow if getProduct is called often or with large k values.
To optimize, we need a way to calculate the product of any window of the last k numbers in constant time. This is similar to how prefix sums allow fast range sum queries, but with multiplication instead of addition.
However, zeros complicate things. If any of the last k numbers is zero, the product is zero, and we cannot divide by zero. We need a strategy that handles zeros efficiently.
We use a prefix product array to store the cumulative product of all numbers added so far. This allows us to compute the product of any subarray in constant time by dividing two prefix products. Here's how we approach it:
prefixProducts where prefixProducts[i] is the product of all numbers from the start up to index i-1.
k numbers, we check if there was a zero among them. If so, return zero. Otherwise, divide the last prefix product by the prefix product k elements before.
i to j, we compute prefixProducts[j+1] / prefixProducts[i].
prefixProducts = [1] (for easier calculations).add(num):
num == 0, reset prefixProducts = [1].prefixProducts[-1] * num to prefixProducts.getProduct(k):
k is greater than or equal to the length of prefixProducts, it means there was a zero within the last k numbers; return 0.prefixProducts[-1] // prefixProducts[-k-1] (use integer division for languages like Python, Java, C++).
This approach ensures that both add and getProduct run in O(1) time per operation.
Let's walk through an example:
add(3) # prefixProducts = [1, 3]
add(0) # prefixProducts = [1] (reset)
add(2) # prefixProducts = [1, 2]
add(5) # prefixProducts = [1, 2, 10]
add(4) # prefixProducts = [1, 2, 10, 40]
getProduct(2) # last 2 numbers: 5, 4 → product = 20
- prefixProducts[-1] = 40
- prefixProducts[-2-1] = prefixProducts[1] = 2
- 40 // 2 = 20
getProduct(3) # last 3 numbers: 2, 5, 4 → product = 40
- prefixProducts[-1] = 40
- prefixProducts[-3-1] = prefixProducts[0] = 1
- 40 // 1 = 40
add(8) # prefixProducts = [1, 2, 10, 40, 320]
getProduct(2) # last 2 numbers: 4, 8 → product = 32
- prefixProducts[-1] = 320
- prefixProducts[-2-1] = prefixProducts[2] = 10
- 320 // 10 = 32
Notice how after adding zero, the prefix products reset. If getProduct(k) is called with k greater than or equal to the current prefixProducts length, it means a zero is in the window, and we return 0.
getProduct(k) operation would take O(k) time, as we would need to multiply k numbers each time.add and getProduct run in O(1) time per operation.The key insight is that by using prefix products and resetting after zeros, we avoid unnecessary recomputation and keep operations efficient.
The "Product of the Last K Numbers" problem is efficiently solved by maintaining a prefix product list that is reset whenever a zero is added. This enables O(1) time complexity for both adding numbers and querying the product of the last k numbers, as we can use division to quickly compute the product of any window. Handling zeros by resetting the prefix product list is the key insight that keeps the solution both correct and efficient.
class ProductOfNumbers:
def __init__(self):
self.prefix_products = [1]
def add(self, num: int) -> None:
if num == 0:
self.prefix_products = [1]
else:
self.prefix_products.append(self.prefix_products[-1] * num)
def getProduct(self, k: int) -> int:
if k >= len(self.prefix_products):
return 0
return self.prefix_products[-1] // self.prefix_products[-k-1]
class ProductOfNumbers {
public:
vector<int> prefixProducts;
ProductOfNumbers() {
prefixProducts.push_back(1);
}
void add(int num) {
if (num == 0) {
prefixProducts.clear();
prefixProducts.push_back(1);
} else {
prefixProducts.push_back(prefixProducts.back() * num);
}
}
int getProduct(int k) {
if (k >= prefixProducts.size()) return 0;
return prefixProducts.back() / prefixProducts[prefixProducts.size() - k - 1];
}
};
class ProductOfNumbers {
private List<Integer> prefixProducts;
public ProductOfNumbers() {
prefixProducts = new ArrayList<>();
prefixProducts.add(1);
}
public void add(int num) {
if (num == 0) {
prefixProducts = new ArrayList<>();
prefixProducts.add(1);
} else {
prefixProducts.add(prefixProducts.get(prefixProducts.size() - 1) * num);
}
}
public int getProduct(int k) {
int size = prefixProducts.size();
if (k >= size) return 0;
return prefixProducts.get(size - 1) / prefixProducts.get(size - k - 1);
}
}
var ProductOfNumbers = function() {
this.prefixProducts = [1];
};
ProductOfNumbers.prototype.add = function(num) {
if (num === 0) {
this.prefixProducts = [1];
} else {
this.prefixProducts.push(this.prefixProducts[this.prefixProducts.length - 1] * num);
}
};
ProductOfNumbers.prototype.getProduct = function(k) {
if (k >= this.prefixProducts.length) return 0;
return Math.floor(this.prefixProducts[this.prefixProducts.length - 1] / this.prefixProducts[this.prefixProducts.length - k - 1]);
};