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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Find Median from Data Stream - Heap & Priority Queue - Leetcode 295 • NeetCode • 219,763 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