2526. Find Consecutive Integers from a Data Stream
Problem Description
The problem provides a scenario where we have to manage a data structure for a stream of integers. The primary goal of this data structure is to check if the last 'k' integers received in the stream are all the same values as a specified 'value'. Two main operations need to be supported:
-
Initialization: The
DataStream
class should be initialized with two integers,value
andk
. There is no stream yet, so we start with an empty one. -
Addition & Check: The class should provide a method
consec
which takes an integernum
and adds it to the stream. The method should returntrue
if the last 'k' integers in the stream are the same asvalue
. If there are fewer than 'k' integers in the stream, or the last 'k' integers are not all equal tovalue
, the method should returnfalse
.
The puzzle lies in efficiently managing the stream and checking the condition with each addition while considering the following:
- The stream is potentially endless, so storing all integers is impractical.
- The check needs to be performed only on the last 'k' elements.
Intuition
The intuition behind the solution is to maintain only the necessary information to determine if the last 'k' integers are equal to value
. In this case, we avoid storing the entire stream, which is a crucial optimization given the infinite potential size of the stream.
Here's the thought process for arriving at the solution:
-
Keep track of the count of consecutive integers equal to
value
as they are added to the stream (self.cnt
). -
The counter must be reset to zero if the incoming number (
num
) is not equal tovalue
. -
Each time a new integer is added to the stream via
consec
method, there are two possibilities:- If the new integer is equal to
value
, increment the counter. - If the new integer is not equal to
value
, reset the counter to zero.
- If the new integer is equal to
-
After adding an integer and updating the counter, check if the count of consecutive
value
is at leastk
. This can be done by comparingself.cnt
withk
. -
Return
true
ifself.cnt
is greater than or equal tok
, signifying that the last 'k' integers are equal tovalue
; otherwise, returnfalse
.
This algorithmic approach ensures that we are using only a constant amount of additional space regardless of the size of the input stream, and that each addition is processed in constant time.
Learn more about Queue and Data Stream patterns.
Solution Approach
The implementation uses a simple class DataStream
with the following components:
-
Initialization (in the
__init__
method):- When a
DataStream
object is created, it is initialized with two instance variables:self.val
: Stores the target value we want to compare the integers in the stream against. It's set to thevalue
parameter passed to the constructor.self.k
: Stores the count 'k' that determines the number of consecutive integers we need to check. It's set to thek
parameter passed to the constructor.
- An additional instance variable
self.cnt
is initialized to zero. This variable keeps track of the number of consecutive integers that matchself.val
.
- When a
-
Addition & checking (in the
consec
method):- The method takes a single integer
num
as its input. - If
num
is the same asself.val
, incrementself.cnt
since we have another occurrence;self.cnt += 1
. - If
num
is not the same asself.val
, we no longer have a consecutive sequence; resetself.cnt
to zero;self.cnt = 0
. - Finally, return if
self.cnt
is at leastself.k
, indicating that the last 'k' integers added were all equal toself.val
. This is a boolean statement:return self.cnt >= self.k
.
- The method takes a single integer
The key here is the counter self.cnt
; it is smartly used to keep a running total of consecutive integers equal to self.val
without the need to maintain the whole stream, hence optimizing both space and time complexity.
This approach follows a common pattern known as the sliding window, although the window is implicit in this case since we are not actively maintaining a list of the last 'k' elements. Instead, we're keeping track of how many of those elements meet our criteria (being equal to self.val
). If at any point a number does not match self.val
, the counter is reset, signifying the start of a new window.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example to illustrate the solution approach. We want to track whether the last k
numbers added to the stream are equal to a certain value value
. For this example, say that value = 5
and k = 3
. We'll perform the following sequence of operations on the data structure:
-
Initialize the
DataStream
object withvalue = 5
andk = 3
.At this point,
self.val = 5
,self.k = 3
, andself.cnt = 0
. The stream is empty. -
Add the integer
5
to the stream by callingconsec(5)
.- Since
5
is equal toself.val
,self.cnt
becomes1
. - There are not yet
k
elements in the stream, so the method returnsfalse
.
- Since
-
Add the integer
5
to the stream by callingconsec(5)
again.- Again,
5
is equal toself.val
, and nowself.cnt
is incremented to2
. - There are still fewer than
k
elements matchingself.val
, so it returnsfalse
.
- Again,
-
Add the integer
3
to the stream by callingconsec(3)
.- Since
3
is not equal toself.val
,self.cnt
is reset to0
. - The method returns
false
because the last three values are not all5
.
- Since
-
Next, add three consecutive
5
integers by callingconsec(5)
thrice.- For the first call, since
5
equalsself.val
,self.cnt
is now1
. - The second call increments
self.cnt
to2
. - With the third call,
self.cnt
will become3
. - At this point,
self.cnt
is equal toself.k
(both are 3), which means the last three added integers are all5
, so the method returnstrue
.
- For the first call, since
To sum up, the DataStream
class managed the stream efficiently. It only kept track of the count of consecutive integers that were equal to self.val
, using self.cnt
. The class did not store all the integers in the stream, thus saving space, and it performed each consec
addition operation in constant time.
Solution Implementation
1class DataStream:
2 def __init__(self, value: int, k: int):
3 # Initialize with a fixed value and consecutive count threshold k
4 self.current_value = value
5 self.threshold_k = k
6 self.consecutive_count = 0 # Counter for consecutive occurrences
7
8 def consec(self, num: int) -> bool:
9 # Resets the counter if the new number is not equal to the current value,
10 # otherwise increments the counter.
11 if num != self.current_value:
12 self.consecutive_count = 0
13 else:
14 self.consecutive_count += 1
15
16 # Return True if the count of consecutive numbers has reached or
17 # surpassed the threshold k
18 return self.consecutive_count >= self.threshold_k
19
20
21# Example of how to use the DataStream class:
22# obj = DataStream(value, k)
23# result = obj.consec(num)
24
1/**
2 * The DataStream class provides a way to track consecutive appearances of a specific value in a stream of integers.
3 * It allows checking if the value has appeared consecutively at least 'k' times after each new number is observed.
4 */
5class DataStream {
6 // cnt tracks the current consecutive count of the value.
7 private int count;
8 // val stores the value to track for consecutive appearances.
9 private int value;
10 // k represents the threshold for consecutive appearances.
11 private int k;
12
13 /**
14 * Constructor to initialize the DataStream with a specific value to track and the threshold of consecutive appearances.
15 *
16 * @param value The value to track for consecutive appearance.
17 * @param k The threshold for consecutive appearances required to return true.
18 */
19 public DataStream(int value, int k) {
20 this.value = value;
21 this.k = k;
22 count = 0; // Initialize the count to 0.
23 }
24
25 /**
26 * Checks if the given number is equal to the tracked value and updates the consecutive count.
27 * If the count matches or exceeds 'k', returns true; otherwise, resets count and returns false.
28 *
29 * @param num The next number in the data stream to compare against the tracked value.
30 * @return True if the tracked value has appeared at least 'k' times consecutively, otherwise False.
31 */
32 public boolean consec(int num) {
33 // If num is equal to the value we're tracking, increment the count. Otherwise, reset the count to 0.
34 count = (num == value) ? count + 1 : 0;
35 // If the count is greater than or equal to k, return true, as we have seen the value 'k' times consecutively.
36 return count >= k;
37 }
38}
39
40/**
41 * Usage:
42 * DataStream obj = new DataStream(value, k);
43 * boolean result = obj.consec(num);
44 */
45
1class DataStream {
2public:
3 // Constructor to initialize the DataStream object with a starting value and the threshold k.
4 DataStream(int value, int k) : currentValue(value), threshold(k), consecutiveCount(0) {
5 // The current consecutive count is initialized to 0.
6 }
7
8 // Function that checks if the current number extends the consecutive sequence of a specific value.
9 // It returns true if the sequence has reached a length of k or more.
10 bool consec(int num) {
11 // If the current number is the same as the value we are tracking,
12 // increment the consecutive count. Otherwise, reset the count to 0.
13 consecutiveCount = (num == currentValue) ? consecutiveCount + 1 : 0;
14
15 // Check if the consecutive count has reached the threshold 'k'.
16 // If it has, return true. Otherwise, return false.
17 return consecutiveCount >= threshold;
18 }
19
20private:
21 int consecutiveCount; // Count of how many consecutive times 'currentValue' has appeared.
22 int currentValue; // The value we are tracking for consecutive appearances.
23 int threshold; // The threshold for how many consecutive appearances are needed.
24};
25
26/**
27 * Your DataStream object will be instantiated and called as such:
28 * DataStream* obj = new DataStream(value, k);
29 * bool param_1 = obj->consec(num);
30 */
31
1// These variables replace private class properties.
2let currentValue: number;
3let threshold: number;
4let consecutiveCount: number;
5
6/**
7 * Initializes the data stream with an initial value and a threshold for consecutive numbers.
8 * @param {number} value - The initial value of the data stream.
9 * @param {number} k - The threshold number of consecutive values.
10 */
11function initializeDataStream(value: number, k: number): void {
12 currentValue = value;
13 threshold = k;
14 consecutiveCount = 0;
15}
16
17/**
18 * Evaluates whether the given number has appeared consecutively at least 'k' times.
19 * @param {number} num - The number to check against the current value in the data stream.
20 * @returns {boolean} - True if 'num' has appeared consecutively at least 'k' times; otherwise, false.
21 */
22function consec(num: number): boolean {
23 if (currentValue === num) {
24 consecutiveCount += 1;
25 } else {
26 consecutiveCount = 0;
27 }
28
29 return consecutiveCount >= threshold;
30}
31
32// Example usage:
33// initializeDataStream(value, k);
34// const isConsecutive = consec(num);
35
Time and Space Complexity
Time Complexity
The consec
method of the DataStream
class has a time complexity of O(1)
. This constant time complexity arises because within the consec
method, all operations (including comparison, conditional operation, and arithmetic addition) are basic and execute in constant time, independent of the input size.
Space Complexity
The space complexity of the DataStream
class is O(1)
. There are a fixed number of instance variables (val
, k
, cnt
) that do not scale with the size of the input. Hence, the amount of memory used does not increase as the size of the data stream increases.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.