Watch 10 video solutions for Find Consecutive Integers from a Data Stream, a medium level problem involving Hash Table, Design, Queue. This walkthrough by BinaryMagic has 887 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |