# Find Consecutive Integers from a Data Stream
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-consecutive-integers-from-a-data-stream)
Canonical: https://scaleengineer.com/dsa/problems/find-consecutive-integers-from-a-data-stream
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream)
**Data structures:** Hash Table, Queue
**Companies:** [Intel](https://scaleengineer.com/companies/intel)
---
## 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 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 <= 109`
* `1 <= k <= 105`
* At most `105` calls will be made to `consec`.

# Approaches
## Using a Queue to Store Last k Elements
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`.
**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.
**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.
### Explanation
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`.

```java
import java.util.Queue;
import java.util.LinkedList;

class DataStream {
    private int value;
    private int k;
    private Queue<Integer> stream;

    public DataStream(int value, int k) {
        this.value = value;
        this.k = k;
        this.stream = new LinkedList<>();
    }

    public boolean consec(int num) {
        stream.add(num);
        if (stream.size() > k) {
            stream.poll();
        }

        if (stream.size() < k) {
            return false;
        }

        for (int n : stream) {
            if (n != this.value) {
                return false;
            }
        }
        return true;
    }
}
```
### 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`.

## Using a Counter for Consecutive Values
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.
**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`.
**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.
### Explanation
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`.

```java
class DataStream {
    private int value;
    private int k;
    private int count;

    public DataStream(int value, int k) {
        this.value = value;
        this.k = k;
        this.count = 0;
    }

    public boolean consec(int num) {
        if (num == this.value) {
            this.count++;
        } else {
            this.count = 0;
        }
        return this.count >= this.k;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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); */
```

### CPP

```cpp
class 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); */
```

### Python

```python
class 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)
```