Find Consecutive Integers from a Data Stream

MEDIUM

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 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

Checkout 2 different approaches to solve Find Consecutive Integers from a Data Stream. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(k) to store the last `k` elements in the queue.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Consecutive Integers from a Data Stream. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Find Consecutive Integers from a Data Stream

Patterns:

DesignCountingData Stream

Data Structures:

Hash TableQueue

Companies:

Intel |