LeetCode 2526 - Find Consecutive Integers from a Data Stream

Difficulty: 🟡 Medium
Topics: Hash Table, Design, Queue, Counting, Data Stream

Solution

Problem Understanding

The problem asks us to design a data structure that continuously processes a stream of integers and determines whether the most recent k integers are all equal to a specific target value.

We are given two parameters when initializing the data structure:

value, which represents the integer we are interested in tracking.
k, which represents how many consecutive occurrences of value we need to see.

The consec(num) method receives one integer at a time from the stream. After inserting the new integer into the stream, we must determine whether the last k integers are all equal to value.

In other words, the question after every insertion becomes:

"Looking only at the most recent k numbers, are they all exactly equal to value?"

If the stream contains fewer than k integers so far, the answer must always be false, because we do not yet have enough numbers to satisfy the requirement.

For example, suppose value = 4 and k = 3.

If the stream becomes:

[4]

we return false, because only one number exists.

If the stream becomes:

[4, 4]

we still return false, because there are only two numbers.

If the stream becomes:

[4, 4, 4]

we return true, because the last three numbers are all 4.

If the stream becomes:

[4, 4, 4, 3]

the last three numbers are [4, 4, 3], so we return false.

The constraints reveal important information about the problem scale:

k can be as large as 10^5
Up to 10^5 calls to consec() can occur
Values themselves can be very large, up to 10^9

Since there may be 100,000 method calls, we should avoid repeatedly scanning the last k elements after every insertion. A naive solution that checks the last k integers every time could become too slow.

There are several edge cases worth identifying early:

When fewer than k numbers have been processed, the answer must always be false.
When k = 1, every occurrence of value immediately returns true, while any other number returns false.
A mismatch in the stream should immediately break the streak, even if many previous numbers matched.
Large values of k make repeated rescanning expensive, so an efficient incremental method is necessary.

Approaches

Brute Force Approach

A straightforward solution is to explicitly maintain the stream of numbers and, after each insertion, examine the last k elements.

Each time consec(num) is called:

Append num to the stream.
If the stream size is less than k, return false.
Otherwise, iterate through the last k elements and check whether every number equals value.

This approach is correct because it directly verifies the problem requirement. We are literally checking whether the most recent k integers all match the target.

However, the problem is efficiency. In the worst case, each consec() call requires scanning k elements. Since there can be up to 10^5 calls and k can also be 10^5, the total complexity becomes too large.

Optimal Approach

The key observation is that we do not need to remember the entire stream or repeatedly inspect the last k elements.

We only care whether the most recent k integers are equal to value.

Instead of storing all values, we can maintain a single variable:

the current number of consecutive occurrences of value.

Every time a new number arrives:

If the number equals value, increment the consecutive count.
Otherwise, reset the count to 0.

Then we simply check:

count >= k

Why does this work?

Because if we have seen at least k consecutive occurrences of value, then the last k integers must all equal value.

Similarly, if a different number appears, the streak is broken immediately, meaning the condition cannot hold.

This transforms the problem from repeatedly rescanning the stream into a constant time update.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k) per call	O(n)	Stores stream and scans last `k` values every query
Optimal	O(1) per call	O(1)	Tracks only consecutive matching count

Algorithm Walkthrough

Optimal Algorithm

Initialize the data structure with the target value, the required streak length k, and a counter count = 0.

The counter represents how many consecutive integers equal to value have appeared most recently. 2. When consec(num) is called, compare num with value.

If num == value, increment count because the streak continues. 3. If num != value, reset count = 0.

This reset is important because any non matching number breaks the consecutive sequence completely. 4. After updating the counter, check whether count >= k.

If true, return true because the last k numbers must all equal value. 5. Otherwise, return false.

This means we either do not yet have enough matching values or the streak was interrupted.

Why it works

The algorithm maintains the invariant that count always equals the number of consecutive occurrences of value ending at the current position in the stream.

If count >= k, then by definition the last k integers are all equal to value. Conversely, if count < k, there cannot be k consecutive matching integers at the end of the stream. Since this invariant is preserved after every insertion, the algorithm always returns the correct result.

Python Solution

class DataStream:

    def __init__(self, value: int, k: int):
        self.value = value
        self.k = k
        self.count = 0

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

        return self.count >= self.k

# Your DataStream object will be instantiated and called as such:
# obj = DataStream(value, k)
# param_1 = obj.consec(num)

The implementation stores three instance variables:

self.value stores the target number we are tracking.
self.k stores the required consecutive length.
self.count tracks the current streak length.

Inside consec(), we compare the incoming number with self.value.

If they match, we increment the streak counter. If not, we reset it to zero because the consecutive sequence has been interrupted.

Finally, we return whether the streak length is at least k. This directly implements the logic from the algorithm walkthrough.

Notice that we never store the full stream. We only maintain the minimal state needed to answer the query efficiently.

Go Solution

type DataStream struct {
	value int
	k     int
	count int
}

func Constructor(value int, k int) DataStream {
	return DataStream{
		value: value,
		k:     k,
		count: 0,
	}
}

func (this *DataStream) Consec(num int) bool {
	if num == this.value {
		this.count++
	} else {
		this.count = 0
	}

	return this.count >= this.k
}

/**
 * Your DataStream object will be instantiated and called as such:
 * obj := Constructor(value, k);
 * param_1 := obj.Consec(num);
 */

The Go implementation follows the exact same logic as the Python solution.

Instead of instance attributes, Go uses struct fields:

value stores the target integer.
k stores the required streak length.
count tracks the current consecutive streak.

The Consec() method uses a pointer receiver so updates to count persist between calls.

Integer overflow is not a concern here because count never exceeds the number of method calls, which is at most 10^5, comfortably within Go's integer range.

Worked Examples

Example 1

Input:

DataStream(4, 3)
consec(4)
consec(4)
consec(4)
consec(3)

We track the value 4 and require k = 3.

Step	Input	Count Before	Action	Count After	Return
1	4	0	Match target, increment	1	false
2	4	1	Match target, increment	2	false
3	4	2	Match target, increment	3	true
4	3	3	Mismatch, reset	0	false

Detailed reasoning:

After the first 4, we only have one matching number, which is less than k.

After the second 4, the streak becomes 2, still less than 3.

After the third 4, the streak becomes 3, which satisfies count >= k, so we return true.

When 3 arrives, the streak breaks completely and resets to 0, so the answer becomes false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Each `consec()` call performs constant time work
Space	O(1)	Only a few integer variables are stored

The time complexity is constant because every operation inside consec() consists of a single comparison, a possible increment or reset, and one final comparison.

The space complexity is also constant because we do not store the stream itself. Regardless of how many numbers arrive, the memory usage remains fixed.

Test Cases

# Provided example
ds = DataStream(4, 3)
assert ds.consec(4) is False  # only 1 element
assert ds.consec(4) is False  # only 2 elements
assert ds.consec(4) is True   # reached k consecutive values
assert ds.consec(3) is False  # streak broken

# k = 1, immediate success on matching value
ds = DataStream(5, 1)
assert ds.consec(5) is True   # single match satisfies k
assert ds.consec(3) is False  # mismatch

# Consecutive streak interrupted
ds = DataStream(2, 3)
assert ds.consec(2) is False
assert ds.consec(2) is False
assert ds.consec(1) is False  # reset streak
assert ds.consec(2) is False
assert ds.consec(2) is False
assert ds.consec(2) is True   # rebuilt streak

# Long streak beyond k
ds = DataStream(7, 2)
assert ds.consec(7) is False
assert ds.consec(7) is True
assert ds.consec(7) is True   # still true after exceeding k

# Never reaches k
ds = DataStream(10, 5)
assert ds.consec(10) is False
assert ds.consec(10) is False
assert ds.consec(9) is False
assert ds.consec(10) is False

# Large values
ds = DataStream(10**9, 2)
assert ds.consec(10**9) is False
assert ds.consec(10**9) is True

# Alternating values
ds = DataStream(1, 2)
assert ds.consec(1) is False
assert ds.consec(2) is False
assert ds.consec(1) is False
assert ds.consec(2) is False

Test	Why
Example case	Validates correctness against the official example
`k = 1`	Ensures immediate matching behavior
Interrupted streak	Verifies reset logic works correctly
Long streak	Confirms values beyond `k` still return `true`
Never reaches `k`	Ensures false is returned correctly
Large values	Validates handling of maximum integer values
Alternating values	Tests repeated resets

Edge Cases

Fewer than `k` elements in the stream

A common mistake is accidentally returning true too early. For example, if k = 5 and only three matching values have appeared, the answer must still be false.

The implementation handles this naturally because count must reach at least k before returning true. Until then, count >= k evaluates to false.

`k = 1`

When k equals 1, every matching number should immediately satisfy the condition.

For example:

value = 10, k = 1
consec(10) → true
consec(5) → false

The implementation works correctly because after a matching value arrives, count becomes 1, which immediately satisfies count >= k.

A mismatch breaking a long streak

Another subtle case occurs when many consecutive matching values have already been seen, but a different number suddenly appears.

For example:

value = 4, k = 3
stream = [4, 4, 4, 9]

After the first three values, the result is true. However, once 9 arrives, the last three values are no longer all 4, so the answer must become false.

The implementation correctly handles this by resetting count to 0 whenever a mismatch occurs, immediately invalidating the streak.

LeetCode 2526 - Find Consecutive Integers from a Data Stream

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Optimal Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Complexity Analysis

Test Cases

Edge Cases

Fewer than k elements in the stream

k = 1

A mismatch breaking a long streak

Fewer than `k` elements in the stream

`k = 1`