2526. Find Consecutive Integers from a Data Stream

MediumDesignQueueHash TableCountingData Stream
Leetcode Link

Problem Description

The problem provides a scenario where we have to manage a data structure for a stream of integers. The primary goal of this data structure is to check if the last 'k' integers received in the stream are all the same values as a specified 'value'. Two main operations need to be supported:

  1. Initialization: The DataStream class should be initialized with two integers, value and k. There is no stream yet, so we start with an empty one.

  2. Addition & Check: The class should provide a method consec which takes an integer num and adds it to the stream. The method should return true if the last 'k' integers in the stream are the same as value. If there are fewer than 'k' integers in the stream, or the last 'k' integers are not all equal to value, the method should return false.

The puzzle lies in efficiently managing the stream and checking the condition with each addition while considering the following:

  • The stream is potentially endless, so storing all integers is impractical.
  • The check needs to be performed only on the last 'k' elements.

Intuition

The intuition behind the solution is to maintain only the necessary information to determine if the last 'k' integers are equal to value. In this case, we avoid storing the entire stream, which is a crucial optimization given the infinite potential size of the stream.

Here's the thought process for arriving at the solution:

  1. Keep track of the count of consecutive integers equal to value as they are added to the stream (self.cnt).

  2. The counter must be reset to zero if the incoming number (num) is not equal to value.

  3. Each time a new integer is added to the stream via consec method, there are two possibilities:

    • If the new integer is equal to value, increment the counter.
    • If the new integer is not equal to value, reset the counter to zero.

  4. After adding an integer and updating the counter, check if the count of consecutive value is at least k. This can be done by comparing self.cnt with k.

  5. Return true if self.cnt is greater than or equal to k, signifying that the last 'k' integers are equal to value; otherwise, return false.

This algorithmic approach ensures that we are using only a constant amount of additional space regardless of the size of the input stream, and that each addition is processed in constant time.

Learn more about Queue and Data Stream patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer techniques do you use to check if a string is a palindrome?

Solution Approach

The implementation uses a simple class DataStream with the following components:

  1. Initialization (in the __init__ method):

    • When a DataStream object is created, it is initialized with two instance variables:
      • self.val: Stores the target value we want to compare the integers in the stream against. It's set to the value parameter passed to the constructor.
      • self.k: Stores the count 'k' that determines the number of consecutive integers we need to check. It's set to the k parameter passed to the constructor.
    • An additional instance variable self.cnt is initialized to zero. This variable keeps track of the number of consecutive integers that match self.val.

  2. Addition & checking (in the consec method):

    • The method takes a single integer num as its input.
    • If num is the same as self.val, increment self.cnt since we have another occurrence; self.cnt += 1.
    • If num is not the same as self.val, we no longer have a consecutive sequence; reset self.cnt to zero; self.cnt = 0.
    • Finally, return if self.cnt is at least self.k, indicating that the last 'k' integers added were all equal to self.val. This is a boolean statement: return self.cnt >= self.k.

The key here is the counter self.cnt; it is smartly used to keep a running total of consecutive integers equal to self.val without the need to maintain the whole stream, hence optimizing both space and time complexity.

This approach follows a common pattern known as the sliding window, although the window is implicit in this case since we are not actively maintaining a list of the last 'k' elements. Instead, we're keeping track of how many of those elements meet our criteria (being equal to self.val). If at any point a number does not match self.val, the counter is reset, signifying the start of a new window.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's consider an example to illustrate the solution approach. We want to track whether the last k numbers added to the stream are equal to a certain value value. For this example, say that value = 5 and k = 3. We'll perform the following sequence of operations on the data structure:

  1. Initialize the DataStream object with value = 5 and k = 3.

    At this point, self.val = 5, self.k = 3, and self.cnt = 0. The stream is empty.

  2. Add the integer 5 to the stream by calling consec(5).

    • Since 5 is equal to self.val, self.cnt becomes 1.
    • There are not yet k elements in the stream, so the method returns false.

  3. Add the integer 5 to the stream by calling consec(5) again.

    • Again, 5 is equal to self.val, and now self.cnt is incremented to 2.
    • There are still fewer than k elements matching self.val, so it returns false.

  4. Add the integer 3 to the stream by calling consec(3).

    • Since 3 is not equal to self.val, self.cnt is reset to 0.
    • The method returns false because the last three values are not all 5.

  5. Next, add three consecutive 5 integers by calling consec(5) thrice.

    • For the first call, since 5 equals self.val, self.cnt is now 1.
    • The second call increments self.cnt to 2.
    • With the third call, self.cnt will become 3.
    • At this point, self.cnt is equal to self.k (both are 3), which means the last three added integers are all 5, so the method returns true.

To sum up, the DataStream class managed the stream efficiently. It only kept track of the count of consecutive integers that were equal to self.val, using self.cnt. The class did not store all the integers in the stream, thus saving space, and it performed each consec addition operation in constant time.

Solution Implementation

1class DataStream:
2    def __init__(self, value: int, k: int):
3        # Initialize with a fixed value and consecutive count threshold k
4        self.current_value = value
5        self.threshold_k = k
6        self.consecutive_count = 0  # Counter for consecutive occurrences
7
8    def consec(self, num: int) -> bool:
9        # Resets the counter if the new number is not equal to the current value,
10        # otherwise increments the counter.
11        if num != self.current_value:
12            self.consecutive_count = 0
13        else:
14            self.consecutive_count += 1
15
16        # Return True if the count of consecutive numbers has reached or
17        # surpassed the threshold k
18        return self.consecutive_count >= self.threshold_k
19
20
21# Example of how to use the DataStream class:
22# obj = DataStream(value, k)
23# result = obj.consec(num)
24
1/**
2 * The DataStream class provides a way to track consecutive appearances of a specific value in a stream of integers.
3 * It allows checking if the value has appeared consecutively at least 'k' times after each new number is observed.
4 */
5class DataStream {
6    // cnt tracks the current consecutive count of the value.
7    private int count;
8    // val stores the value to track for consecutive appearances.
9    private int value;
10    // k represents the threshold for consecutive appearances.
11    private int k;
12
13    /**
14     * Constructor to initialize the DataStream with a specific value to track and the threshold of consecutive appearances.
15     * 
16     * @param value The value to track for consecutive appearance.
17     * @param k     The threshold for consecutive appearances required to return true.
18     */
19    public DataStream(int value, int k) {
20        this.value = value;
21        this.k = k;
22        count = 0; // Initialize the count to 0.
23    }
24
25    /**
26     * Checks if the given number is equal to the tracked value and updates the consecutive count.
27     * If the count matches or exceeds 'k', returns true; otherwise, resets count and returns false.
28     * 
29     * @param num The next number in the data stream to compare against the tracked value.
30     * @return    True if the tracked value has appeared at least 'k' times consecutively, otherwise False.
31     */
32    public boolean consec(int num) {
33        // If num is equal to the value we're tracking, increment the count. Otherwise, reset the count to 0.
34        count = (num == value) ? count + 1 : 0;
35        // If the count is greater than or equal to k, return true, as we have seen the value 'k' times consecutively.
36        return count >= k;
37    }
38}
39
40/**
41 * Usage:
42 * DataStream obj = new DataStream(value, k);
43 * boolean result = obj.consec(num);
44 */
45
1class DataStream {
2public:
3    // Constructor to initialize the DataStream object with a starting value and the threshold k.
4    DataStream(int value, int k) : currentValue(value), threshold(k), consecutiveCount(0) {
5        // The current consecutive count is initialized to 0.
6    }
7
8    // Function that checks if the current number extends the consecutive sequence of a specific value.
9    // It returns true if the sequence has reached a length of k or more.
10    bool consec(int num) {
11        // If the current number is the same as the value we are tracking,
12        // increment the consecutive count. Otherwise, reset the count to 0.
13        consecutiveCount = (num == currentValue) ? consecutiveCount + 1 : 0;
14      
15        // Check if the consecutive count has reached the threshold 'k'.
16        // If it has, return true. Otherwise, return false.
17        return consecutiveCount >= threshold;
18    }
19
20private:
21    int consecutiveCount;    // Count of how many consecutive times 'currentValue' has appeared.
22    int currentValue;        // The value we are tracking for consecutive appearances.
23    int threshold;           // The threshold for how many consecutive appearances are needed.
24};
25
26/**
27 * Your DataStream object will be instantiated and called as such:
28 * DataStream* obj = new DataStream(value, k);
29 * bool param_1 = obj->consec(num);
30 */
31
1// These variables replace private class properties.
2let currentValue: number;
3let threshold: number;
4let consecutiveCount: number;
5
6/**
7 * Initializes the data stream with an initial value and a threshold for consecutive numbers.
8 * @param {number} value - The initial value of the data stream.
9 * @param {number} k - The threshold number of consecutive values.
10 */
11function initializeDataStream(value: number, k: number): void {
12    currentValue = value;
13    threshold = k;
14    consecutiveCount = 0;
15}
16
17/**
18 * Evaluates whether the given number has appeared consecutively at least 'k' times.
19 * @param {number} num - The number to check against the current value in the data stream.
20 * @returns {boolean} - True if 'num' has appeared consecutively at least 'k' times; otherwise, false.
21 */
22function consec(num: number): boolean {
23    if (currentValue === num) {
24        consecutiveCount += 1;
25    } else {
26        consecutiveCount = 0;
27    }
28
29    return consecutiveCount >= threshold;
30}
31
32// Example usage:
33// initializeDataStream(value, k);
34// const isConsecutive = consec(num);
35
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

Time Complexity

The consec method of the DataStream class has a time complexity of O(1). This constant time complexity arises because within the consec method, all operations (including comparison, conditional operation, and arithmetic addition) are basic and execute in constant time, independent of the input size.

Space Complexity

The space complexity of the DataStream class is O(1). There are a fixed number of instance variables (val, k, cnt) that do not scale with the size of the input. Hence, the amount of memory used does not increase as the size of the data stream increases.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Median of Data Stream

Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫