2526. Find Consecutive Integers from a Data Stream
Description
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 integersvalue
andk
.boolean consec(int num)
Addsnum
to the stream of integers. Returnstrue
if the lastk
integers are equal tovalue
, andfalse
otherwise. If there are less thank
integers, the condition does not hold true, so returnsfalse
.
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 <= 109
1 <= k <= 105
- At most
105
calls will be made toconsec
.
Solutions
Solution 1: Counting
We can maintain a counter $\textit{cnt}$ to record the current number of consecutive integers equal to $\textit{value}$.
When calling the consec
method, if $\textit{num}$ is equal to $\textit{value}$, we increment $\textit{cnt}$ by 1; otherwise, we reset $\textit{cnt}$ to 0. Then we check whether $\textit{cnt}$ is greater than or equal to $\textit{k}$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|