We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Consecutive Integers from a Data Stream

Difficulty: Medium

Problem Description

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 with methods to initialize the object and to add integers to the stream while checking the condition.

Key Insights

  • The last k integers need to be tracked to determine if they are equal to a specified value.
  • If the number of parsed integers is less than k, the method should return false.
  • Efficiently maintaining the count of consecutive integers can simplify the solution.

Space and Time Complexity

Time Complexity: O(1) for each call to the consec method, as it involves updating a few counters and performing constant-time checks. Space Complexity: O(1), since we only need a constant amount of space to store counters and the last value.

Solution

To solve the problem, we will maintain a count of consecutive integers that match the specified value. We will use two variables: one for counting how many consecutive integers equal the value and another to keep track of the total number of integers parsed. Each time a new integer is added, we will check if it is equal to the specified value and update our count accordingly. If the count reaches k, we return true; if it drops below k or if we haven't yet parsed k integers, we return false.

Code Solutions

class DataStream:
    def __init__(self, value: int, k: int):
        # Initialize the value to check and the required count k
        self.value = value
        self.k = k
        self.count = 0  # Counter for consecutive equal values
        self.total = 0   # Total count of integers parsed

    def consec(self, num: int) -> bool:
        # Increment the total count of integers parsed
        self.total += 1
        
        # Check if the current number is the same as the value
        if num == self.value:
            self.count += 1  # Increment the count if it matches
        else:
            self.count = 0  # Reset the count if it doesn't match
        
        # Check if we have parsed at least k integers and if the last k are equal to value
        if self.total >= self.k:
            return self.count >= self.k  # Return true if count of consecutive equals value is k or more
        
        return False  # Not enough integers parsed yet
← Back to All Questions