2526. Find Consecutive Integers from a Data Stream

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:

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.

Example 1:

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.

Constraints:

1 <= value, num <= 10⁹
1 <= k <= 10⁵
At most 10⁵ calls will be made to consec.

Solutions

Solution 1: Counting

We can maintain a counter \(\textit{cnt}\) to record the current number of consecutive integers equal to \(\textit{value}\).

When calling the consec method, if \(\textit{num}\) is equal to \(\textit{value}\), we increment \(\textit{cnt}\) by 1; otherwise, we reset \(\textit{cnt}\) to 0. Then we check whether \(\textit{cnt}\) is greater than or equal to \(\textit{k}\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

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

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


# Your DataStream object will be instantiated and called as such:
# obj = DataStream(value, k)
# param_1 = obj.consec(num)

class DataStream {
    private int cnt;
    private int val;
    private int k;

    public DataStream(int value, int k) {
        val = value;
        this.k = k;
    }

    public boolean consec(int num) {
        cnt = num == val ? cnt + 1 : 0;
        return cnt >= k;
    }
}

/**
 * Your DataStream object will be instantiated and called as such:
 * DataStream obj = new DataStream(value, k);
 * boolean param_1 = obj.consec(num);
 */

class DataStream {
public:
    DataStream(int value, int k) {
        val = value;
        this->k = k;
    }

    bool consec(int num) {
        cnt = num == val ? cnt + 1 : 0;
        return cnt >= k;
    }

private:
    int cnt = 0;
    int val, k;
};

/**
 * Your DataStream object will be instantiated and called as such:
 * DataStream* obj = new DataStream(value, k);
 * bool param_1 = obj->consec(num);
 */

type DataStream struct {
    val, k, cnt int
}

func Constructor(value int, k int) DataStream {
    return DataStream{value, k, 0}
}

func (this *DataStream) Consec(num int) bool {
    if num == this.val {
        this.cnt++
    } else {
        this.cnt = 0
    }
    return this.cnt >= this.k
}

/**
 * Your DataStream object will be instantiated and called as such:
 * obj := Constructor(value, k);
 * param_1 := obj.Consec(num);
 */

class DataStream {
    private val: number;
    private k: number;
    private cnt: number;

    constructor(value: number, k: number) {
        this.val = value;
        this.k = k;
        this.cnt = 0;
    }

    consec(num: number): boolean {
        this.cnt = this.val === num ? this.cnt + 1 : 0;
        return this.cnt >= this.k;
    }
}

/**
 * Your DataStream object will be instantiated and called as such:
 * var obj = new DataStream(value, k)
 * var param_1 = obj.consec(num)
 */

2526. Find Consecutive Integers from a Data Stream

Description

Solutions

Solution 1: Counting

Comments