LeetCode 2526. Find Consecutive Integers from a Data Stream Solution in Java, C++, Python & More | Explanation + Code

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 <= 109
• 1 <= k <= 105
• At most 105 calls will be made to consec.

Solutions

Solution 1: Counting

We can maintain a counter cnt to record the current number of consecutive integers equal to value.

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

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

PythonJavaC++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)(code-box)

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); */(code-box)

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); */(code-box)

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); */(code-box)

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) */(code-box)