Find Consecutive Integers from a Data Stream

Med

#2306Time: O(k) for each call to `consec`. Adding to and removing from the queue takes O(1) time, but the check requires iterating through all `k` elements in the queue in the worst case.Space: O(k) to store the last `k` elements in the queue.1 company

Patterns

Design Counting Data Stream

Data structures

Hash Table Queue

Companies

Intel

Prompt

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 <= 10⁹
1 <= k <= 10⁵
At most 10⁵ calls will be made to consec.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves maintaining a data structure, specifically a queue, to keep track of the most recent k integers from the stream. For each new integer, we add it to the queue and ensure the queue's size does not exceed k. Then, we check if the queue has exactly k elements and if all of them are equal to the target value.

Algorithm

Initialize value, k, and an empty queue stream.
For each call to consec(num):
- Add num to the stream.
- If stream.size() > k, remove the head of the queue.
- If stream.size() < k, return false.
- Iterate through each element x in the stream:
  - If x != value, return false.
- Return true.

Walkthrough

We initialize the DataStream with value, k, and a queue (like LinkedList or ArrayDeque).

In the consec(num) method:

Add the new integer num to the end of the queue.
If the queue's size becomes larger than k, remove the element from the front. This keeps the queue containing only the last k (or fewer) elements.
Check if the current size of the queue is less than k. If it is, we haven't seen enough elements yet, so we return false.
If the size is k, we iterate through all elements in the queue. If any element is not equal to the target value, we return false.
If the loop completes without finding any mismatch, it means all k elements are equal to value, so we return true.

1import java.util.Queue;2import java.util.LinkedList;3 4class DataStream {5    private int value;6    private int k;7    private Queue<Integer> stream;8 9    public DataStream(int value, int k) {10        this.value = value;11        this.k = k;12        this.stream = new LinkedList<>();13    }14 15    public boolean consec(int num) {16        stream.add(num);17        if (stream.size() > k) {18            stream.poll();19        }20 21        if (stream.size() < k) {22            return false;23        }24 25        for (int n : stream) {26            if (n != this.value) {27                return false;28            }29        }30        return true;31    }32}

Complexity

Time

O(k) for each call to `consec`. Adding to and removing from the queue takes O(1) time, but the check requires iterating through all `k` elements in the queue in the worst case.

Space

O(k) to store the last `k` elements in the queue.

Trade-offs

Pros

Conceptually simple and easy to implement.
Correctly solves the problem by directly simulating the condition.

Cons

Inefficient for large values of k as each consec call takes time proportional to k.
Uses more memory than necessary, as we only need to know if the streak is maintained, not the actual numbers.

A more efficient approach is to avoid storing the actual numbers. Instead, we can just maintain a count of how many consecutive times the target value has appeared at the end of the stream. This eliminates the need for a separate data structure and reduces the time complexity of each check to constant time.

Algorithm

Initialize value, k, and a counter count = 0.
For each call to consec(num):
- If num == value, increment count.
- Else, reset count to 0.
- Return true if count >= k, otherwise return false.

Walkthrough

We initialize the DataStream with value, k, and a counter variable, say count, set to 0.

In the consec(num) method:

We check if the incoming integer num is equal to our target value.
If num == value, it means the consecutive streak continues, so we increment count.
If num != value, the streak is broken. We must reset count to 0.
After updating the counter, we check if count is greater than or equal to k. If it is, this implies that the last k (or more) numbers were all equal to value, so we return true. Otherwise, we return false.

1class DataStream {2    private int value;3    private int k;4    private int count;5 6    public DataStream(int value, int k) {7        this.value = value;8        this.k = k;9        this.count = 0;10    }11 12    public boolean consec(int num) {13        if (num == this.value) {14            this.count++;15        } else {16            this.count = 0;17        }18        return this.count >= this.k;19    }20}

Complexity

Time

O(1) for each call to `consec`. Each call involves a few simple arithmetic operations and comparisons, which are constant time operations.

Space

O(1) extra space. We only need to store the counter, `value`, and `k`, which is constant space regardless of the number of calls or the value of `k`.

Trade-offs

Pros

Extremely efficient with O(1) time and space complexity.
Simple logic that is easy to implement and maintain.

Cons

There are no significant cons to this approach as it is optimal for the given problem constraints.

Solutions

Solution

1class DataStream { private int cnt ; private int val ; private int k ; public DataStream ( int value , int k ) { val = value ; this . k = k ; } public boolean consec ( int num ) { cnt = num == val ? cnt + 1 : 0 ; return cnt >= k ; } } /** * Your DataStream object will be instantiated and called as such: * DataStream obj = new DataStream(value, k); * boolean param_1 = obj.consec(num); */

1class DataStream { public: DataStream ( int value , int k ) { val = value ; this -> k = k ; } bool consec ( int num ) { cnt = num == val ? cnt + 1 : 0 ; return cnt >= k ; } private: int cnt = 0 ; int val , k ; }; /** * Your DataStream object will be instantiated and called as such: * DataStream* obj = new DataStream(value, k); * bool param_1 = obj->consec(num); */

1class DataStream : def __init__ ( self , value : int , k : int ): self . val , self . k = value , k self . cnt = 0 def consec ( self , num : int ) -> bool : self . cnt = 0 if num != self . val else self . cnt + 1 return self . cnt >= self . k # Your DataStream object will be instantiated and called as such: # obj = DataStream(value, k) # param_1 = obj.consec(num)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem