Problem statement

Integers arrive one at a time. After each arrival you must say whether the last k integers of the stream are all equal to a fixed value.

Write the class DataStream:

• DataStream(int value, int k) starts an empty stream watching for k copies of value in a row.
• boolean consec(int num) appends num to the stream and returns true if the last k integers are all equal to value. If fewer than k integers have arrived so far, it returns false.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["DataStream","consec","consec","consec","consec","consec"]
[[4,3],[4],[4],[4],[3],[4]]
Output: [null,false,false,true,false,false]
Explanation: The first two calls see fewer than 3 integers. The third completes 4, 4, 4. Then 3 arrives, and the last three are 4, 4, 3; after the next 4 they are 4, 3, 4.

Example 2

Input: ["DataStream","consec","consec","consec"]
[[1000000000,1],[1000000000],[7],[1000000000]]
Output: [null,true,false,true]
Explanation: With k = 1, each answer is just whether the newest integer equals value.

Constraints

• 1 <= value, num <= 10^9
• 1 <= k <= 10^5
• At most 10^5 calls are made to consec

Hints for Find Consecutive Integers from a Data Stream

1. Hint 1

   Keeping the last k integers and checking them all costs O(k) per call.

2. Hint 2

   Only one thing about the window matters: how long the current run of value at the end of the stream is.

3. Hint 3

   Keep a counter: reset it to 0 when num != value, otherwise add 1. The answer is counter >= k.

How to solve Find Consecutive Integers from a Data Stream

The last k integers are all value exactly when the stream ends in a run of at least k copies of value. A single counter of that trailing run answers every call in O(1).

Approach

1. Keep run = 0.
2. consec(num): if num == value, increase run; otherwise set run = 0.
3. Return run >= k.

Why it works

After each call run is the number of consecutive copies of value at the end of the stream: a match extends that suffix by one, anything else ends it. The last k integers are all value if and only if that suffix has length at least k (and it cannot when fewer than k integers have arrived).

Complexity

• Time — O(1) per call
• Space — O(1)

Pitfalls

• Return false until at least k integers have arrived — the counter handles that automatically because it cannot exceed the number of calls.
• Do not store the stream: 10^5 calls with k up to 10^5 make a window scan quadratic.

Reference solution

Python

class DataStream:

    def __init__(self, value: int, k: int):
        self.value = value
        self.k = k
        self.run = 0  # copies of value at the end of the stream

    def consec(self, num: int) -> bool:
        self.run = self.run + 1 if num == self.value else 0
        return self.run >= self.k

Java

class DataStream {
    private int value, k, run = 0; // run: copies of value at the end of the stream

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

    public boolean consec(int num) {
        run = num == value ? run + 1 : 0;
        return run >= k;
    }
}

C++

class DataStream {
    int value, k, run = 0; // run: copies of value at the end of the stream
public:
    DataStream(int value, int k) : value(value), k(k) {}

    bool consec(int num) {
        run = num == value ? run + 1 : 0;
        return run >= k;
    }
};

JavaScript

var DataStream = function(value, k) {
    this.value = value;
    this.k = k;
    this.run = 0; // copies of value at the end of the stream
};

DataStream.prototype.consec = function(num) {
    this.run = num === this.value ? this.run + 1 : 0;
    return this.run >= this.k;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium
• Design a Food Rating System Medium