Leetcode 1352: Product of the Last K Numbers
Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers in the stream.
Problem
Approach
Steps
Complexity
Input: The input consists of a sequence of operations: initialize the object, add numbers to the stream, and get the product of the last k numbers.
Example: For example, ['ProductOfNumbers', 'add', 'add', 'add', 'getProduct'] with input [[], [3], [0], [2], 2].
Constraints:
• 0 <= num <= 100
• 1 <= k <= 4 * 10^4
• At most 4 * 10^4 calls to add and getProduct.
Output: The output should be a list of integers where each element is the result of the respective 'getProduct' operation.
Example: For example, ['getProduct(2)', 'getProduct(3)'] could return 20 and 40, respectively.
Constraints:
• The result will always fit in a 32-bit integer.
Goal: Design an efficient system to keep track of the last k numbers and compute their product.
Steps:
• 1. Use a list to keep track of the products of the numbers in the stream.
• 2. If a zero is encountered, reset the product history.
• 3. For each getProduct query, compute the product of the last k numbers.
Goal: The solution should handle up to 4 * 10^4 operations efficiently.
Steps:
• The product at any point should fit within a 32-bit integer.
Assumptions:
• The input list has at least k numbers when calling 'getProduct'.
• Any sequence of numbers in the list fits within the range of a 32-bit integer.
• Input: Example 1: ['ProductOfNumbers', 'add', 'add', 'add', 'add', 'add', 'getProduct(2)', 'getProduct(3)', 'getProduct(4)', 'add', 'getProduct(2)']
• Explanation: The operations add numbers to the stream, and getProduct computes the product of the last k numbers.
• Input: Example 2: ['ProductOfNumbers', 'add', 'add', 'add', 'getProduct(3)']
• Explanation: After adding numbers [1, 2, 3], the product of the last 3 numbers is 6.
Approach: The solution should efficiently store the running product and handle reset conditions when a zero is encountered.
Observations:
• A running product can be stored in a list where each index represents the product of numbers up to that point.
• A zero encountered resets the running product.
• We can track the product of the numbers in the stream in a way that allows us to compute the product of any k consecutive numbers.
Steps:
• 1. Maintain a list where the product of the stream up to each number is stored.
• 2. When a zero is encountered, reset the product list.
• 3. For each 'getProduct' call, use the list to quickly compute the product of the last k numbers.
Empty Inputs:
• No numbers added yet: Ensure no product is returned until numbers are added.
Large Inputs:
• Handling up to 4 * 10^4 operations efficiently without performance degradation.
Special Values:
• Zero in the stream: Reset the product list.
Constraints:
• Ensure that the product of the stream at any point in time fits within a 32-bit integer.
public:
ProductOfNumbers() {
p = {1};
}
void add(int num) {
if(num > 0) {
p.push_back(p.back() * num);
} else {
p = {1};
}
}
int getProduct(int k) {
int n = p.size();
return k < n ? p[n - 1] / p[n - k - 1]: 0;
}
};
/**
* Your ProductOfNumbers object will be instantiated and called as such:
* ProductOfNumbers* obj = new ProductOfNumbers();
* obj->add(num);
* int param_2 = obj->getProduct(k);
1 : Access Modifier
public:
Declares the public access modifier for the class members.
2 : Constructor
ProductOfNumbers() {
Defines the constructor for the `ProductOfNumbers` class, initializing the cumulative product list.
3 : Initialization
p = {1};
Initializes the product list with 1 to handle cumulative product calculations.
4 : Method Declaration
void add(int num) {
Begins the declaration of the `add` method to handle new number additions.
5 : Condition Check
if(num > 0) {
Checks if the added number is positive to update the cumulative product list.
6 : Update Product
p.push_back(p.back() * num);
Appends the product of the last cumulative product and the new number to the list.
7 : Reset List
} else {
Handles the case where the added number is zero or negative by resetting the list.
8 : Reset Product
p = {1};
Resets the cumulative product list to its initial state.
9 : Method Declaration
int getProduct(int k) {
Begins the declaration of the `getProduct` method to compute the product of the last k numbers.
10 : Size Calculation
int n = p.size();
Calculates the size of the cumulative product list.
11 : Return Value
return k < n ? p[n - 1] / p[n - k - 1]: 0;
Returns the product of the last k numbers if valid; otherwise, returns 0.
Best Case: O(1) when adding a number.
Average Case: O(1) for each operation.
Worst Case: O(k) when computing the product of the last k numbers.
Description: The time complexity is dominated by the 'getProduct' operation, which is O(k) in the worst case.
Best Case: O(1)
Worst Case: O(n) where n is the number of elements in the stream.
Description: The space complexity is O(n) as we need to store the product for each element in the stream.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus