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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Consecutive Integers from a Data Stream

Number: 2620

Difficulty: Medium

Paid? No

Companies: Intel

Problem Description

Implement a DataStream class that processes a stream of integers. Given an integer value and an integer k, every time a new integer is added to the stream, check if the last k integers are equal to the given value. If the stream contains fewer than k integers, the method should return false.

Key Insights

  • Use a counter to track consecutive occurrences of the target value.
  • When a new integer is processed, if it matches the target value, increment the counter; otherwise, reset the counter.
  • Return true only when the counter reaches k, ensuring the last k integers all match the target value.
  • Avoid storing the entire stream to achieve constant time complexity per operation.

Space and Time Complexity

Time Complexity: O(1) per consec call. Space Complexity: O(1).

Solution

We maintain an integer counter (consecutiveCount) that tracks how many consecutive times the target value has been seen. On each call to consec, we check if the current number is equal to the target value. If it is, we increment the counter; if not, we reset the counter to zero. We then return true if the counter is at least k, which means the last k consecutive integers are all equal to the target value. This solution is efficient since each call only requires constant time and constant space.

Code Solutions

class DataStream:
    def __init__(self, value: int, k: int):
        # Initialize with the target value and k consecutive numbers.
        self.value = value
        self.k = k
        # Counter to track consecutive occurrences of the target value.
        self.count = 0

    def consec(self, num: int) -> bool:
        # If the current number equals the target, increment the counter.
        if num == self.value:
            self.count += 1
        else:
            # Otherwise, reset the counter.
            self.count = 0
        # Return true if the counter is at least k.
        return self.count >= self.k

# Example usage:
# dataStream = DataStream(4, 3)
# print(dataStream.consec(4)) # False, only one 4 encountered.
← Back to All Questions