Problem Description

You need to design a data structure that monitors a stream of integers and checks whether the most recent k integers are all equal to a specific target value.

The DataStream class should support two operations:

1. Constructor DataStream(int value, int k): Initializes the data structure with:

   • value: the target integer that we want to check for
   • k: the number of consecutive integers we need to examine
   • An initially empty stream of integers

2. Method consec(int num):

   • Adds a new integer num to the stream
   • Returns true if the last k integers in the stream are ALL equal to value
   • Returns false if:
     • Any of the last k integers is different from value, OR
     • There are fewer than k integers in the stream so far

The solution uses a counting approach with a counter cnt that tracks how many consecutive integers equal to value we've seen most recently. When a new number arrives:

• If the number equals value, increment the counter
• If the number is different from value, reset the counter to 0
• Return whether the counter is at least k

This approach is efficient because it only needs to track one counter instead of storing the entire stream or the last k elements.

Intuition

The key insight is recognizing that we don't actually need to store the last k integers from the stream. Instead, we only care about one specific property: are ALL of the last k integers equal to value?

Think about what happens as we process the stream:

• If we encounter a number that's not equal to value, we know for certain that the last k integers cannot all be equal to value (at least not until we've seen k more integers that are all equal to value)
• If we encounter a number equal to value, we're building up a consecutive sequence

This observation leads us to realize we only need to track how many consecutive occurrences of value we've seen most recently. It's like keeping a "streak counter":

• When we see value, we extend our current streak
• When we see any other number, our streak breaks and resets to 0
• We have a valid sequence when our streak reaches or exceeds k

For example, if value = 5 and k = 3, and we receive the stream [5, 5, 4, 5, 5, 5, 5]:

• After [5, 5]: counter = 2 (not enough yet, return false)
• After [5, 5, 4]: counter = 0 (streak broken, return false)
• After [5, 5, 4, 5]: counter = 1 (new streak started, return false)
• After [5, 5, 4, 5, 5]: counter = 2 (building up, return false)
• After [5, 5, 4, 5, 5, 5]: counter = 3 (we have 3 consecutive 5s, return true)
• After [5, 5, 4, 5, 5, 5, 5]: counter = 4 (still valid, return true)

This approach is elegant because it uses O(1) space regardless of the stream size or the value of k.

Learn more about Queue and Data Stream patterns.

Solution Approach

The implementation uses a simple counting strategy with just two instance variables to track the state:

1. Instance Variables:

   • self.val: Stores the target value we're checking for
   • self.k: Stores the required number of consecutive occurrences
   • self.cnt: Counter to track the current streak of consecutive values equal to self.val

2. Constructor (__init__):

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

   • Initializes the target value and required count
   • Sets the counter to 0 since we haven't seen any numbers yet

3. The consec Method:

   def consec(self, num: int) -> bool:
       self.cnt = 0 if num != self.val else self.cnt + 1
       return self.cnt >= self.k

   This method performs two key operations:

   Step 1: Update the counter

   • If num != self.val: Reset self.cnt to 0 (streak is broken)
   • If num == self.val: Increment self.cnt by 1 (extend the streak)

   This is elegantly written as a conditional expression:

   self.cnt = 0 if num != self.val else self.cnt + 1

   Step 2: Check the condition

   • Return True if self.cnt >= self.k (we have at least k consecutive values)
   • Return False otherwise

Time and Space Complexity:

• Time Complexity: O(1) for each consec call - we only perform constant-time operations
• Space Complexity: O(1) - we only store three variables regardless of the stream size

The beauty of this solution is its simplicity. By recognizing that we only need to track the current consecutive count rather than storing actual values, we achieve both optimal time and space efficiency.

Example Walkthrough

Let's walk through a concrete example with value = 3 and k = 2. We want to check if the last 2 integers are both equal to 3.

Initial State:

• val = 3, k = 2, cnt = 0

Stream: [3, 3, 1, 3, 3]

Step 1: consec(3) is called

• Check: num (3) == val (3)? Yes
• Update: cnt = cnt + 1 = 0 + 1 = 1
• Check: cnt (1) >= k (2)? No
• Return: false (we've only seen one 3 so far)

Step 2: consec(3) is called

• Check: num (3) == val (3)? Yes
• Update: cnt = cnt + 1 = 1 + 1 = 2
• Check: cnt (2) >= k (2)? Yes
• Return: true (the last 2 integers are both 3)

Step 3: consec(1) is called

• Check: num (1) == val (3)? No
• Update: cnt = 0 (streak broken)
• Check: cnt (0) >= k (2)? No
• Return: false (the last 2 integers are [3, 1], not both 3)

Step 4: consec(3) is called

• Check: num (3) == val (3)? Yes
• Update: cnt = cnt + 1 = 0 + 1 = 1
• Check: cnt (1) >= k (2)? No
• Return: false (the last 2 integers are [1, 3], not both 3)

Step 5: consec(3) is called

• Check: num (3) == val (3)? Yes
• Update: cnt = cnt + 1 = 1 + 1 = 2
• Check: cnt (2) >= k (2)? Yes
• Return: true (the last 2 integers are [3, 3], both equal to 3)

The key insight is that we don't need to store the actual stream values. The counter cnt tells us everything we need: when it reaches k, we know the last k values must all be equal to our target value. When we see a different number, resetting to 0 ensures we start counting fresh consecutive occurrences.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The consec method performs a constant number of operations:

• One comparison (num != self.val)
• One conditional assignment (either setting self.cnt = 0 or self.cnt = self.cnt + 1)
• One comparison (self.cnt >= self.k)
• One return statement

All these operations take constant time regardless of the input size or the values of k and value. The method doesn't contain any loops or recursive calls, so each call to consec executes in constant time.

Space Complexity: O(1)

The DataStream class uses a fixed amount of memory:

• Three instance variables: self.val, self.k, and self.cnt
• Each variable stores a single integer value

The space usage doesn't grow with the number of calls to consec or with the size of the input parameters. The class maintains only these three variables throughout its lifetime, using constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Counter Reset Logic

The Mistake: A common error is resetting the counter after checking the condition, or implementing the reset logic incorrectly:

def consec(self, num: int) -> bool:
    if num == self.target_value:
        self.consecutive_count += 1
    result = self.consecutive_count >= self.min_consecutive
    if num != self.target_value:
        self.consecutive_count = 0  # Reset AFTER checking - WRONG!
    return result

This creates a bug where if we have exactly k consecutive values followed by a different value, the method incorrectly returns True for that different value.

Example:

• DataStream(value=5, k=2)
• consec(5) → False (count=1)
• consec(5) → True (count=2)
• consec(3) → True (WRONG! Should be False)

The Fix: Always reset the counter BEFORE checking the condition:

def consec(self, num: int) -> bool:
    if num != self.target_value:
        self.consecutive_count = 0
    else:
        self.consecutive_count += 1
    return self.consecutive_count >= self.min_consecutive

Pitfall 2: Not Handling Edge Cases Properly

The Mistake: Forgetting that the counter can grow indefinitely and not considering potential integer overflow in languages with fixed integer sizes, or trying to "optimize" by capping the counter:

def consec(self, num: int) -> bool:
    if num == self.target_value:
        self.consecutive_count = min(self.consecutive_count + 1, self.min_consecutive)  # WRONG optimization
    else:
        self.consecutive_count = 0
    return self.consecutive_count >= self.min_consecutive

While this might seem like an optimization, it doesn't actually provide any benefit in Python and could cause confusion. In some cases, knowing the exact count might be useful for debugging or future extensions.

The Fix: Keep the implementation simple and let the counter grow naturally:

def consec(self, num: int) -> bool:
    self.consecutive_count = 0 if num != self.target_value else self.consecutive_count + 1
    return self.consecutive_count >= self.min_consecutive

Pitfall 3: Misunderstanding the "Last k Values" Requirement

The Mistake: Some might incorrectly think they need to store the last k values and check them all:

def __init__(self, value: int, k: int):
    self.target_value = value
    self.min_consecutive = k
    self.last_k_values = []  # Unnecessary storage!

def consec(self, num: int) -> bool:
    self.last_k_values.append(num)
    if len(self.last_k_values) > self.min_consecutive:
        self.last_k_values.pop(0)
  
    if len(self.last_k_values) < self.min_consecutive:
        return False
  
    return all(v == self.target_value for v in self.last_k_values)  # O(k) time!

This approach uses O(k) space and O(k) time per operation, which is inefficient.

The Fix: Recognize that you only need to track consecutive occurrences with a single counter, achieving O(1) space and time complexity.