Leetcode 2526: Find Consecutive Integers from a Data Stream
You need to implement a DataStream class that processes a stream of integers and checks whether the last k integers in the stream are equal to a specified value.
Problem
Approach
Steps
Complexity
Input: The input consists of two integers: `value`, the target value to check for, and `k`, the number of consecutive integers to be checked.
Example: [3, 4]
Constraints:
• 1 <= value, num <= 10^9
• 1 <= k <= 10^5
• At most 10^5 calls will be made to consec.
Output: The output should be a boolean value: `true` if the last k integers are equal to the target value, otherwise `false`. If fewer than k integers have been parsed, return `false`.
Example: false
Constraints:
• The output is a boolean value representing the result of the consec method.
Goal: Check if the last k integers in the stream are equal to the target value.
Steps:
• Store the target value and the integer k.
• Maintain a count of consecutive integers equal to the target value.
• For each call to consec(), add the integer to the stream and update the count. If the count reaches k, return true. If not, return false.
Goal: Ensure that all input values respect the given constraints for value, num, and k.
Steps:
• 1 <= value, num <= 10^9
• 1 <= k <= 10^5
• At most 10^5 calls will be made to consec.
Assumptions:
• The input values are within the given constraints.
• The number of consec calls will not exceed 10^5.
• Input: [3, 4], [3], [3], [3], [4]
• Explanation: The DataStream object is initialized with value 3 and k = 4. It returns false until 4 consecutive values of 3 are encountered.
• Input: [5, 2], [5], [5]
• Explanation: The DataStream object is initialized with value 5 and k = 2. It returns false initially, then returns true after two consecutive values of 5.
Approach: Use a counter to track the number of consecutive occurrences of the target value. Reset the counter when the current value is not equal to the target.
Observations:
• A simple solution involves tracking consecutive integers and resetting the count when the condition fails.
• We will use a counter to store the number of consecutive target values and return true when the counter reaches k.
Steps:
• Initialize the target value and k.
• Use a counter to track the number of consecutive integers equal to the target value.
• In the consec method, update the counter based on the input integer. If the counter reaches k, return true, else return false.
Empty Inputs:
• There are no cases with empty inputs as each consec method call requires a number to be added.
Large Inputs:
• Ensure that the solution can handle large inputs efficiently, especially when there are up to 10^5 consec calls.
Special Values:
• Handle cases where k is 1 or the input numbers are equal to the target value.
Constraints:
• Ensure that the solution meets the time complexity constraints and handles the maximum number of consec calls.
int val, k, cnt = 0;
DataStream(int value, int k) {
val = value;
this->k = k;
}
bool consec(int num) {
if(val == num) cnt = min(k, cnt+1);
else {
cnt = 0;
}
return k == cnt;
}
};
/**
* Your DataStream object will be instantiated and called as such:
* DataStream* obj = new DataStream(value, k);
* bool param_1 = obj->consec(num);
1 : Variable Initialization
int val, k, cnt = 0;
This initializes three integer variables: 'val' to store the value, 'k' for the threshold number of consecutive appearances, and 'cnt' to track the current count of consecutive appearances, initially set to 0.
2 : Constructor
DataStream(int value, int k) {
This is the constructor of the DataStream class, which initializes the 'val' and 'k' variables when an instance of the class is created.
3 : Variable Assignment
val = value;
This assigns the passed 'value' to the 'val' variable, which will be the number tracked for consecutive occurrences.
4 : Variable Assignment
this->k = k;
This assigns the passed 'k' value (threshold for consecutive occurrences) to the instance variable 'k'.
5 : Method Definition
bool consec(int num) {
This is the definition of the 'consec' method, which checks if the given number 'num' has appeared consecutively 'k' times.
6 : Condition Check
if(val == num) cnt = min(k, cnt+1);
This checks if the current 'num' matches 'val'. If true, it increments 'cnt' (count of consecutive appearances), but ensures that 'cnt' does not exceed the threshold 'k'.
7 : Reset Count
cnt = 0;
If 'num' is not equal to 'val', the count of consecutive appearances is reset to 0.
8 : Return Statement
return k == cnt;
This checks if 'cnt' (the current consecutive count) equals 'k'. If true, the method returns true, indicating that 'num' has appeared 'k' times consecutively.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is constant for each consec call as it involves updating a counter and checking a condition.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we only store a few integer variables.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus