2620. Find Consecutive Integers From A Data Stream¶

LeetCode Problem View on GitHub

2620. Find Consecutive Integers from a Data Stream

Medium

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.

Solution¶

class DataStream {
    static class Pair {
        int node, freq;
        public Pair(int node, int freq) {
            this.node = node;
            this.freq = freq;
        }
        @Override
        public String toString() {
            return "(" + node + " " + freq + ")";
        }
    }

    private Stack<Pair> st;
    private int need, time;
    public DataStream(int value, int k) {
        st = new Stack<>();
        this.need = value;
        this.time = k;
    }

    public boolean consec(int num) {
        if (st.size() == 0) {
            st.add(new Pair(num, 1));
        } else {
            if (st.peek().node == num) {
                st.add(new Pair(st.peek().node, st.peek().freq + 1));
            } else {
                st.add(new Pair(num, 1));
            }
        }
        if (st.peek().node == need && st.peek().freq >= time)
            return true;
        return false;
    }
}

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

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here