For a stream of integers, implement a data structure that checks if the last k integers parsed in the stream are equal to value.
Implement the DataStream class:
DataStream(int value, int k) Initializes the object with an empty integer stream and the two integers value and k.boolean consec(int num) Adds num to the stream of integers. Returns true if the last k integers are equal to value, and false otherwise. If there are less than k integers, the condition does not hold true, so returns false.
Example 1:
Input
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
Output
[null, false, false, true, false]
Explanation
DataStream dataStream = new DataStream(4, 3); //value = 4, k = 3
dataStream.consec(4); // Only 1 integer is parsed, so returns False.
dataStream.consec(4); // Only 2 integers are parsed.
// Since 2 is less than k, returns False.
dataStream.consec(4); // The 3 integers parsed are all equal to value, so returns True.
dataStream.consec(3); // The last k integers parsed in the stream are [4,4,3].
// Since 3 is not equal to value, it returns False.
Constraints:
1 <= value, num <= 1091 <= k <= 105105 calls will be made to consec.Problem Overview: You design a data stream class that receives integers one by one. Each time a new value arrives, return true if the last k elements in the stream are equal to a given target value. Otherwise return false. The challenge is maintaining this check efficiently as the stream grows.
Approach 1: Sliding Window Technique with Queue (O(1) time per query, O(k) space)
This approach treats the last k elements of the stream as a sliding window. Maintain a queue that stores the most recent values and ensure its size never exceeds k. When a new number arrives, push it into the queue and pop the oldest element if the size exceeds k. Track how many elements inside the window match the target value. If the queue size is exactly k and the match count equals k, return true.
The key insight: you only care about the most recent k values, not the entire stream. Updating the queue and the counter requires constant work, so each call to consec() runs in O(1) time. This solution naturally fits problems involving a queue or data stream where a fixed-size window must be tracked.
Approach 2: Counter with FIFO Queue (O(1) time per query, O(k) space)
This variation separates the logic slightly: maintain a FIFO queue for the last k elements and a counter tracking how many equal the target value. Insert the new element into the queue and increment the counter if it matches the target. If the queue grows beyond k, remove the oldest element and decrement the counter if that removed value was the target.
After each update, check whether the counter equals k. If it does, the last k numbers are all the target value. The logic relies on constant-time updates rather than scanning the window each time. This pattern appears frequently in counting problems and streaming checks where recomputation would be too expensive.
Recommended for interviews: The sliding window with a queue is the expected approach. It demonstrates that you recognize the fixed-size window constraint and maintain it efficiently. A brute-force scan of the last k elements after each insertion would cost O(k) per query and quickly become inefficient. Interviewers typically want to see constant-time updates using a queue and a running counter, which shows solid understanding of window maintenance in streaming scenarios.
The sliding window technique is efficient for problems where we need to keep track of a subset of contiguous elements. By employing a queue of size at most k, we can maintain the most recent k numbers and check if they are all equal to the target value. This approach handles incoming stream data dynamically and efficiently.
This C solution uses a circular queue to store the last k elements received from the data stream. When a new element is added using the consec function, the program checks if all elements in the queue are equal to the specified value. If so, it returns true; otherwise, false.
The time complexity of each operation is O(k) due to the number of checks involved. The space complexity is O(k) because we store up to k elements.
By employing both a queue for keeping recent elements and a separate counter for counting occurrences of the target value, the solution can achieve efficiency when determining if k most recent elements are identical to a specified value. As new numbers are added, outdated ones are removed while maintaining count integrity, making this approach efficient for large input sizes.
This solution uses a circular buffer (array) and a counter variable to check if the latest k numbers match the target value. With each addition, the algorithm updates the buffer and counter, retaining O(1) efficiency for both add and check operations.
Time complexity is O(1) for each operation due to the efficient buffer update and check. The space complexity is O(k) due to storing the latest k elements.
We can maintain a counter cnt to record the current number of consecutive integers equal to value.
When calling the consec method, if num is equal to value, we increment cnt by 1; otherwise, we reset cnt to 0. Then we check whether cnt is greater than or equal to k.
The time complexity is O(1), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Technique with Queue | The time complexity of each operation is O(k) due to the number of checks involved. The space complexity is O(k) because we store up to k elements. |
| Counter with FIFO Queue | Time complexity is O(1) for each operation due to the efficient buffer update and check. The space complexity is O(k) due to storing the latest k elements. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Queue | O(1) per query | O(k) | Best general solution for maintaining the last k elements in a stream |
| Counter with FIFO Queue | O(1) per query | O(k) | When tracking counts of a specific value in a fixed-size streaming window |
Find Consecutive Integers from a Data Stream || leetcode Biweekly 95 || Leetcode Medium • BinaryMagic • 887 views views
Watch 9 more video solutions →Practice Find Consecutive Integers from a Data Stream with our built-in code editor and test cases.
Practice on FleetCode