Find Consecutive Integers from a Data Stream

Find Consecutive Integers from a Data Stream - Problem

Hash Table Design Queue Counting Data Stream Medium

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.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["DataStream", "consec", "consec", "consec", "consec"], params = [[4, 3], [4], [3], [5], [4]]

› Output: [null, false, false, false, false]

💡 Note: Initialize with value=4, k=3. Add 4 (count=1<3, false), add 3 (count=0<3, false), add 5 (count=0<3, false), add 4 (count=1<3, false)

Example 2 — Consecutive Match

$ Input: operations = ["DataStream", "consec", "consec", "consec", "consec"], params = [[4, 3], [4], [4], [4], [3]]

› Output: [null, false, false, true, false]

💡 Note: After three consecutive 4s, count=3≥k=3 returns true. Adding 3 resets count=0, returns false

Example 3 — Edge Case k=1

$ Input: operations = ["DataStream", "consec", "consec"], params = [[5, 1], [5], [6]]

› Output: [null, true, false]

💡 Note: With k=1, first matching number immediately returns true. Non-matching number returns false

Constraints

1 ≤ value ≤ 10⁹
1 ≤ k ≤ 10⁵
1 ≤ num ≤ 10⁹
At most 10⁵ calls to consec

Visualization

Tap to expand

Understanding the Visualization

Initialize

Create DataStream with target value=4 and k=3

Process Stream

Add numbers one by one, track consecutive matches

Return Result

True when k consecutive numbers match target value

Key Takeaway

🎯 Key Insight: Track consecutive count with O(1) space instead of storing all numbers

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to track consecutive matching count instead of storing all numbers. The optimal counter-based approach uses O(1) time per operation and O(1) space by incrementing a counter for matches and resetting it for non-matches.

Common Approaches

Approach	Time	Space	Notes
✓ Store All Numbers	O(k)	O(n)	Store all numbers and check last k elements each time
Sliding Window with Queue	O(k)	O(k)	Use a queue to maintain exactly the last k numbers
Counter-Based Approach	O(1)	O(1)	Track consecutive count without storing all numbers

Store All Numbers — Algorithm Steps

Store every incoming number in a list
For each query, examine the last k numbers
Return true only if all k numbers match the target value

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create empty stream, set value=4, k=3

Add Numbers

Add each number to stream and check last k

Check Pattern

Scan last k numbers to see if all equal value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int value;
    int k;
    int* stream;
    int size;
    int capacity;
} DataStream;

DataStream* createDataStream(int value, int k) {
    DataStream* ds = (DataStream*)malloc(sizeof(DataStream));
    ds->value = value;
    ds->k = k;
    ds->stream = (int*)malloc(1000 * sizeof(int));
    ds->size = 0;
    ds->capacity = 1000;
    return ds;
}

bool consec(DataStream* ds, int num) {
    ds->stream[ds->size++] = num;
    if (ds->size < ds->k) {
        return false;
    }
    
    for (int i = ds->size - ds->k; i < ds->size; i++) {
        if (ds->stream[i] != ds->value) {
            return false;
        }
    }
    return true;
}

int main() {
    printf("[null,false,false,false,true,false]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Each consec call checks the last k elements

✓ Linear Growth

Space Complexity

O(n)

Stores all n numbers received in the stream

⚡ Linearithmic Space

18.4K Views

Medium Frequency

~15 min Avg. Time

385 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Store All Numbers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler