Find Consecutive Integers from a Data Stream solution and explanation
9 more videos on this problem
Find Consecutive Integers from a Data Stream || leetcode Biweekly 95 || Leetcode MediumBinaryMagic · 12:00 · 888 views
B. Find Consecutive Integers from a Data Stream - LEETCODE BIWEEKLY CONTEST 95 (Code + Explanation)Joyjit Codes · 6:20 · 588 views
Find Consecutive Integers from a data stream | Leetcode ContestA Code Daily! · 6:06 · 520 views
2526. Find Consecutive Integers From A Data Stream (Leetcode Medium)Programming Live with Larry · 6:42 · 381 views
Find Consecutive Integers from a Data Stream | Leetcode 2526 | Leetcode Biweekly contest 95Tech Courses · 6:19 · 346 views
2526 Find Consecutive Integers from a Data Stream | LeetCode | C++ | Beginner Friendly ExplanationDeep Tech · 8:45 · 277 views
2526. Find Consecutive Integers from a Data Stream | Biweekly Contest 95 | LeetCode | DCC NIT-ADCC NITA · 4:26 · 273 views
Leetcode 2526 Find Consecutive Integers from a Data Stream (Java) - O(1) TIME AND SPACETheAnalyticGuy · 5:16 · 247 views
Leetcode 2526. Find Consecutive Integers from a Data StreamElite Code · 18:22 · 221 views
Leetcode 6288 || Find Consecutive Integers from a Data Stream|| Leetcode Contest Medium || cppCoding Techniques with Komal | Newton School · 4:50 · 199 views
The problem
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 integersvalueandk.boolean consec(int num)Addsnumto the stream of integers. Returnstrueif the lastkintegers are equal tovalue, andfalseotherwise. If there are less thankintegers, 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 <= 1091 <= k <= 105- At most
105calls will be made toconsec.
Approach overview
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 1: Sliding Window Technique with Queue
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.
from collections import deque
class DataStream:
def __init__(self, value: int, k: int):
self.queue = deque()
self.k = k
self.value = value
self.count = 0
def consec(self, num: int) -> bool:
self.queue.append(num)
if num == self.value:
self.count += 1
if len(self.queue) > self.k:
if self.queue.popleft() == self.value:
self.count -= 1
return len(self.queue) == self.k and self.count == self.kimport java.util.*;
class DataStream {
private Queue<Integer> queue;
private int k;
private int value;
private int count;
public DataStream(int value, int k) {
this.queue = new LinkedList<>();
this.k = k;
this.value = value;
this.count = 0;
}
public boolean consec(int num) {
queue.offer(num);
if (num == value) count++;
if (queue.size() > k) {
if (queue.poll() == value) count--;
}
return queue.size() == k && count == k;
}
}#include <queue>
using namespace std;
class DataStream {
private:
queue<int> q;
int k;
int value;
int count;
public:
DataStream(int value, int k) {
this->value = value;
this->k = k;
this->count = 0;
}
bool consec(int num) {
q.push(num);
if (num == value) count++;
if (q.size() > k) {
if (q.front() == value) count--;
q.pop();
}
return q.size() == k && count == k;
}
};class DataStream {
constructor(value, k) {
this.queue = [];
this.k = k;
this.value = value;
this.count = 0;
}
consec(num) {
this.queue.push(num);
if (num === this.value) this.count++;
if (this.queue.length > this.k) {
if (this.queue.shift() === this.value) this.count--;
}
return this.queue.length === this.k && this.count === this.k;
}
}#include <stdbool.h>
#include <stdlib.h>
typedef struct {
int *queue;
int front;
int size;
int k;
int value;
} DataStream;
DataStream* dataStreamCreate(int value, int k) {
DataStream* obj = (DataStream*)malloc(sizeof(DataStream));
obj->queue = (int*)calloc(k, sizeof(int));
obj->front = 0;
obj->size = 0;
obj->k = k;
obj->value = value;
return obj;
}
bool consec(DataStream* obj, int num) {
if (obj->size < obj->k) {
obj->queue[(obj->front + obj->size) % obj->k] = num;
obj->size++;
} else {
obj->queue[obj->front] = num;
obj->front = (obj->front + 1) % obj->k;
}
if (obj->size == obj->k) {
for (int i = 0; i < obj->k; i++) {
if (obj->queue[(obj->front + i) % obj->k] != obj->value) {
return false;
}
}
return true;
}
return false;
}
void dataStreamFree(DataStream* obj) {
free(obj->queue);
free(obj);
}using System.Collections.Generic;
public class DataStream {
private Queue<int> queue;
private int k;
private int value;
private int count;
public DataStream(int value, int k) {
this.queue = new Queue<int>();
this.k = k;
this.value = value;
this.count = 0;
}
public bool Consec(int num) {
queue.Enqueue(num);
if (num == value) count++;
if (queue.Count > k) {
if (queue.Dequeue() == value) count--;
}
return queue.Count == k && count == k;
}
}The Python solution employs a deque to manage the last k elements as well as a counter to track occurrences of the target value. As numbers are added, the deque pops older elements. If all the k numbers in the deque match the target, the method returns true.
The time complexity is O(1) for each consec call, thanks to deque operations, and the space complexity is O(k).
Approach 2: Counter with FIFO Queue
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.
from collections import deque
class DataStream:
def __init__(self, value: int, k: int):
self.queue = deque()
self.k = k
self.value = value
self.count = 0
def consec(self, num: int) -> bool:
self.queue.append(num)
if num == self.value:
self.count += 1
if len(self.queue) > self.k:
if self.queue.popleft() == self.value:
self.count -= 1
return len(self.queue) == self.k and self.count == self.kimport java.util.*;
class DataStream {
private Queue<Integer> queue;
private int k;
private int value;
private int count;
public DataStream(int value, int k) {
this.queue = new LinkedList<>();
this.k = k;
this.value = value;
this.count = 0;
}
public boolean consec(int num) {
queue.offer(num);
if (num == value) count++;
if (queue.size() > k) {
if (queue.poll() == value) count--;
}
return queue.size() == k && count == k;
}
}#include <queue>
using namespace std;
class DataStream {
private:
queue<int> q;
int k;
int value;
int count;
public:
DataStream(int value, int k) {
this->value = value;
this->k = k;
this->count = 0;
}
bool consec(int num) {
q.push(num);
if (num == value) count++;
if (q.size() > k) {
if (q.front() == value) count--;
q.pop();
}
return q.size() == k && count == k;
}
};class DataStream {
constructor(value, k) {
this.queue = [];
this.k = k;
this.value = value;
this.count = 0;
}
consec(num) {
this.queue.push(num);
if (num === this.value) this.count++;
if (this.queue.length > this.k) {
if (this.queue.shift() === this.value) this.count--;
}
return this.queue.length === this.k && this.count === this.k;
}
}#include <stdbool.h>
#include <stdlib.h>
typedef struct {
int *arr;
int size;
int front;
int rear;
int value;
int k;
int count;
} DataStream;
DataStream* dataStreamCreate(int value, int k) {
DataStream* obj = (DataStream*)malloc(sizeof(DataStream));
obj->arr = (int*)malloc(k * sizeof(int));
obj->size = 0;
obj->front = 0;
obj->rear = -1;
obj->value = value;
obj->k = k;
obj->count = 0;
return obj;
}
bool consec(DataStream* obj, int num) {
if (num == obj->value) obj->count++;
if (obj->size == obj->k) {
if (obj->arr[obj->front] == obj->value) obj->count--;
obj->front = (obj->front + 1) % obj->k;
} else {
obj->size++;
}
obj->rear = (obj->rear + 1) % obj->k;
obj->arr[obj->rear] = num;
return obj->size == obj->k && obj->count == obj->k;
}
void dataStreamFree(DataStream* obj) {
free(obj->arr);
free(obj);
}using System.Collections.Generic;
public class DataStream {
private Queue<int> queue;
private int k;
private int value;
private int count;
public DataStream(int value, int k) {
this.queue = new Queue<int>();
this.k = k;
this.value = value;
this.count = 0;
}
public bool Consec(int num) {
queue.Enqueue(num);
if (num == value) count++;
if (queue.Count > k) {
if (queue.Dequeue() == value) count--;
}
return queue.Count == k && count == k;
}
}This Python implementation relies on a deque for FIFO handling of the last k elements, in conjunction with a counter to monitor occurrences of the target value. It checks efficiently if these k numbers match the target using constant time operations.
The time complexity is O(1) for each consec call, leveraging efficient operations of the deque structure. The space complexity stands at O(k), realising storage for k recent elements.
Approach 3: Counting
We can maintain a counter cnt to record the current number of consecutive integers equal to value.
When calling the consec method, if num is equal to value, we increment cnt by 1; otherwise, we reset cnt to 0. Then we check whether cnt is greater than or equal to k.
The time complexity is O(1), and the space complexity is O(1).
class DataStream {
private val: number;
private k: number;
private cnt: number;
constructor(value: number, k: number) {
this.val = value;
this.k = k;
this.cnt = 0;
}
consec(num: number): boolean {
this.cnt = this.val === num ? this.cnt + 1 : 0;
return this.cnt >= this.k;
}
}
/**
* Your DataStream object will be instantiated and called as such:
* var obj = new DataStream(value, k)
* var param_1 = obj.consec(num)
*/type DataStream struct {
val, k, cnt int
}
func Constructor(value int, k int) DataStream {
return DataStream{value, k, 0}
}
func (this *DataStream) Consec(num int) bool {
if num == this.val {
this.cnt++
} else {
this.cnt = 0
}
return this.cnt >= this.k
}
/**
* Your DataStream object will be instantiated and called as such:
* obj := Constructor(value, k);
* param_1 := obj.Consec(num);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Technique with Queue | The time complexity is O(1) for each |
| Counter with FIFO Queue | The time complexity is O(1) for each |
| Counting | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Consecutive Integers from a Data Stream easy or hard?
The problem is rated Medium because it combines class design with sliding window logic. The algorithm itself is straightforward once you recognize that only the last k elements matter, but managing the queue and counter correctly requires careful implementation.
Find Consecutive Integers from a Data Stream Python/Java solution
In Python and Java, implement a class that stores a queue of size k and a counter for matches. Each call to the method that receives a new integer updates the queue and counter, then checks whether the counter equals k. The logic runs in O(1) time and works identically across languages.
How to solve Find Consecutive Integers from a Data Stream in O(1)?
Maintain a fixed-size queue containing the last k numbers and keep a counter of how many equal the target value. When a new number arrives, push it into the queue and update the counter. If the queue exceeds size k, remove the oldest value and adjust the counter. If the counter equals k, return true.
What is the best approach for Find Consecutive Integers from a Data Stream?
The best approach uses a sliding window with a queue and a running counter. Store the last k elements in a queue and track how many equal the target value. Each new stream update adjusts the counter and possibly removes the oldest value. This allows constant O(1) time per query with O(k) space.
Is Find Consecutive Integers from a Data Stream asked at Google/Amazon/Meta?
Data stream design problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving sliding windows, counters, and real-time updates are common because they test system design thinking and efficient state maintenance.
What data structure is used in Find Consecutive Integers from a Data Stream?
The core data structure is a queue that stores the most recent k elements of the stream. A simple integer counter tracks how many of those elements equal the target value. Some implementations also reference counting patterns similar to hash table or frequency tracking techniques.
What is the time complexity of Find Consecutive Integers from a Data Stream?
The optimal solution processes each incoming number in O(1) time. Queue insertion, removal of the oldest element, and updating the counter all take constant time. Space complexity is O(k) because only the most recent k elements are stored.