Skip to main content
Talentd

Find Consecutive Integers from a Data Stream - Solution & Explanation

MediumHash TableDesignQueueCounting17 min readAsked at: Intel
Practice this problem

Problem Statement

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.

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.

This C solution uses a circular queue to store the last k elements received from the data stream. When a new element is added using the consec function, the program checks if all elements in the queue are equal to the specified value. If so, it returns true; otherwise, false.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of each operation is O(k) due to the number of checks involved. The space complexity is O(k) because we store up to k elements.

Try this approach in the editor →

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.

This solution uses a circular buffer (array) and a counter variable to check if the latest k numbers match the target value. With each addition, the algorithm updates the buffer and counter, retaining O(1) efficiency for both add and check operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(1) for each operation due to the efficient buffer update and check. The space complexity is O(k) due to storing the latest k elements.

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Technique with Queue

The time complexity of each operation is O(k) due to the number of checks involved. The space complexity is O(k) because we store up to k elements.

Counter with FIFO Queue

Time complexity is O(1) for each operation due to the efficient buffer update and check. The space complexity is O(k) due to storing the latest k elements.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with QueueO(1) per queryO(k)Best general solution for maintaining the last k elements in a stream
Counter with FIFO QueueO(1) per queryO(k)When tracking counts of a specific value in a fixed-size streaming window

Video Solution

Find Consecutive Integers from a Data Stream || leetcode Biweekly 95 || Leetcode Medium • BinaryMagic • 888 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find Consecutive Integers from a Data Stream with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Zero-Filled Subarrays