Find Consecutive Integers from a Data Stream

medium queue design counting

Problem

Design a DataStream(value, k) class over a stream of integers. Each call to consec(num) appends num to the stream and returns true only when the last k integers are all equal to value. If fewer than k integers have been parsed, it returns false.

Inputvalue = 4, k = 3, calls = consec(4), consec(4), consec(4), consec(3)

Output[false, false, true, false]

After the third 4 the last 3 values are [4,4,4] → true; then 3 makes them [4,4,3] → false.

value

consec calls (comma-separated)

from collections import deque

class DataStream:
    def __init__(self, value, k):
        self.value = value
        self.k = k
        self.q = deque()    # last k parsed integers
        self.cnt = 0        # how many in q equal value
    def consec(self, num):
        self.q.append(num)
        if num == self.value:
            self.cnt += 1
        if len(self.q) > self.k:        # window overflowed
            old = self.q.popleft()
            if old == self.value:
                self.cnt -= 1
        return len(self.q) == self.k and self.cnt == self.k

class DataStream {
  constructor(value, k) {
    this.value = value;
    this.k = k;
    this.q = [];    // last k parsed integers
    this.cnt = 0;   // how many in q equal value
  }
  consec(num) {
    this.q.push(num);
    if (num === this.value) this.cnt++;
    if (this.q.length > this.k) {        // window overflowed
      const old = this.q.shift();
      if (old === this.value) this.cnt--;
    }
    return this.q.length === this.k && this.cnt === this.k;
  }
}

class DataStream {
    private Deque<Integer> q = new ArrayDeque<>();
    private int value, k, cnt = 0;      // cnt = items in q equal to value
    public DataStream(int value, int k) {
        this.value = value;
        this.k = k;
    }
    public boolean consec(int num) {
        q.offer(num);
        if (num == value) cnt++;
        if (q.size() > k) {             // window overflowed
            int old = q.poll();
            if (old == value) cnt--;
        }
        return q.size() == k && cnt == k;
    }
}

class DataStream {
    queue<int> q;                       // last k parsed integers
    int value, k, cnt = 0;              // cnt = items in q equal to value
public:
    DataStream(int value, int k) : value(value), k(k) {}
    bool consec(int num) {
        q.push(num);
        if (num == value) cnt++;
        if ((int)q.size() > k) {        // window overflowed
            int old = q.front(); q.pop();
            if (old == value) cnt--;
        }
        return (int)q.size() == k && cnt == k;
    }
};

Explanation

We must answer, after each new number, whether the last k integers are all equal to value. Re-scanning the last k items on every call would be O(k) per call; instead we maintain the window incrementally so each call is constant time.

Keep a queue q holding only the most recent k parsed integers, plus a counter cnt for how many items currently in q are equal to value.

On consec(num) we push num onto the back of the queue and, if it equals value, bump cnt. If the queue now holds more than k items, the window has overflowed, so we pop the oldest item from the front and, if that item equalled value, decrement cnt.

The answer is true exactly when the queue holds a full window of k items and every one of them equals value — that is, len(q) == k and cnt == k. While fewer than k integers have arrived the queue is short and the answer is false.

Example with value = 4, k = 3 and calls 4, 4, 4, 3: after one and two 4s the window is not yet full, so false; after the third 4 the window is [4,4,4] with cnt = 3, so true; then 3 slides the window to [4,4,3] with cnt = 2, so false.

Time: O(1) per call Space: O(k)