Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

Solution

Method 1 – Sliding Window with Counter

Intuition

To efficiently check if the last k numbers in the stream are equal to a target value, we use a counter to track consecutive occurrences of the value. When a new number arrives, we increment the counter if it matches the target, otherwise reset it. If the counter reaches k, we return true.

Approach

  1. Store the target value and k.
  2. Maintain a counter for consecutive occurrences of the value.
  3. On each call to consec(num):
    • If num equals value, increment the counter.
    • Otherwise, reset the counter to 0.
    • Return true if the counter is at least k, else false.

Complexity

  • ⏰ Time complexity: O(1) per operation, as all updates and checks are constant time.
  • 🧺 Space complexity: O(1), only a few variables are stored.

Code

1
2
3
4
5
6
7
8
9

class DataStream {
    int value, k, cnt = 0;
public:
    DataStream(int value, int k) : value(value), k(k) {}
    bool consec(int num) {
        cnt = (num == value) ? cnt + 1 : 0;
        return cnt >= k;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class DataStream {
    private final int value, k;
    private int cnt = 0;
    public DataStream(int value, int k) {
        this.value = value;
        this.k = k;
    }
    public boolean consec(int num) {
        cnt = (num == value) ? cnt + 1 : 0;
        return cnt >= k;
    }
}
1
2
3
4
5
6
7
8

class DataStream:
    def __init__(self, value: int, k: int) -> None:
        self.value = value
        self.k = k
        self.cnt = 0
    def consec(self, num: int) -> bool:
        self.cnt = self.cnt + 1 if num == self.value else 0
        return self.cnt >= self.k