Easy to Understand With Examples using Three TreeSet
Intuition\n\nLet\'s walk through the intuition behind this solution with a concrete example. Suppose we\'re given m = 5 and k = 1, and we start receiving a stre
# Intuition\n\nLet\'s walk through the intuition behind this solution with a concrete example. Suppose we\'re given `m = 5` and `k = 1`, and we start receiving a stream of integers.\n\n### Initial Stream: `[3, 1, 10, 7, 2]`\n\n- Our objective is to calculate the MKAverage for the last `m = 5` elements in the stream, after removing the smallest `k = 1` and largest `k = 1` elements.\n\n#### Step 1: Add Elements to the Stream\n- As elements `3, 1, 10, 7, 2` are added to the stream, they\'re also added to the `middles` set since we haven\'t reached `m` elements yet.\n\n#### Step 2: Calculate MKAverage\n- Once we reach `m` elements, we calculate the MKAverage:\n  1. Remove the smallest `k` and largest `k` elements: remove `1` and `10`.\n  2. Calculate the average of the remaining: `(3 + 7 + 2) / 3 = 4`.\n\n### Adding Another Element: Stream becomes `[3, 1, 10, 7, 2, 5]`\n- Now, we exceed `m` elements. The oldest element (`3`) must be considered for removal.\n\n#### Handling the New Element\n- The new element `5` is added, and we need to maintain our sets according to the rules:\n  1. **If adding to `middles` directly:** We ensure the sets `smaller` and `larger` are properly populated with the smallest and largest `k` elements, respectively.\n  2. **Adjustment:** Since `3` (the oldest) is removed, we check where it belonged (in this case, it was part of `middles`). We then adjust the sets to ensure they still contain correct elements. In this scenario, we might find no need to adjust since `5` fits into `middles` directly.\n  \n#### Recalculate MKAverage\n- Now, the stream considered for MKAverage is `[1, 10, 7, 2, 5]`.\n  1. Remove smallest `k=1` (`1`) and largest `k=1` (`10`).\n  2. Calculate the average of `[7, 2, 5]`: `(7 + 2 + 5) / 3 = 4.66`, rounded down to `4`.\n\n### Why This Works\n- **Efficiency:** This approach avoids recalculating from scratch for each new element or MKAverage calculation. By maintaining the sets, we can quickly adjust to new elements and efficiently calculate the MKAverage.\n- **Dynamic Adjustments:** As new elements come in, we dynamically adjust which elements belong in the smallest, middle, and largest sets. This flexibility ensures we always have the correct elements for calculating the MKAverage, even as the stream changes.\n\nThis example highlights how we manage a stream of data in an efficient and dynamic manner, allowing for quick updates and calculations without needing to sort or fully re-evaluate the data set with each new element or calculation request.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe solution uses three instances of a custom MultiSet class to manage the smallest, middle, and largest elements and their sums. The MultiSet class uses a TreeSet to maintain sorted order of elements, allowing for efficient retrieval and removal of the smallest and largest elements. This class also tracks the sum of the elements it contains, which is crucial for calculating the average.\n\n**Initialization**: When an MKAverage object is created, the sizes of the three multisets are initialized based on the given m and k. The queue holds the last m elements of the stream.\n\n**Adding an Element**: Each new element is added to a queue to ensure we only consider the last m elements and to the middles set initially. If the queue exceeds m elements, the oldest element is removed, and adjustments are made among the three multisets to maintain their size constraints and sort order. This involves moving elements between the sets based on their values to ensure smaller and larger always contain the smallest and largest k elements, respectively.\n\n**Calculating MKAverage**: If there are fewer than m elements in the stream, the method returns -1. Otherwise, the MKAverage is calculated by dividing the sum of the middles set by its size (which is m - 2k).\n\n# Complexity\n- Time Compexity - O(logM)\n\n- Space complexity:  - O(M)\n\n\n# Code\n```\nclass MKAverage {\n    Queue<Node> queue = new LinkedList<>();\n    int containerSize = 0;\n    MultiSet smaller = new MultiSet();\n    MultiSet middles = new MultiSet();\n    MultiSet larger = new MultiSet();\n    int index = 0;\n    \n    public MKAverage(int m, int k) {\n        this.index = 0;\n        this.containerSize = m;\n        queue.clear();\n\n        smaller.clear();\n        smaller.setMaxSize(k);\n        \n        larger.clear();\n        larger.setMaxSize(k);\n        \n        middles.clear();\n        middles.setMaxSize(k);\n    }\n\n    public void addElement(int num) {\n        Node newNode = new Node(num,index++);\n        queue.add(newNode);\n        middles.add(newNode);\n        if(queue.size() < containerSize) return;\n        if(queue.size() == containerSize){\n            while(smaller.size() < smaller.getMaxSize()){\n                smaller.add(middles.pollFirst());\n            }\n            while(larger.size() < larger.getMaxSize()){\n                larger.add(middles.pollLast());\n            }\n            return;\n        }\n        \n        Node lastNode = queue.poll();\n        if(smaller.contains(lastNode)){\n            smaller.remove(lastNode);\n            smaller.add(middles.pollFirst());\n        } else if(larger.contains(lastNode)){\n            larger.remove(lastNode);\n            larger.add(middles.pollLast());\n        } else middles.remove(lastNode);\n\n        if(smaller.lastValue() > middles.firstValue()){\n            smaller.add(middles.pollFirst());\n            middles.add(smaller.pollLast());\n        } else if(larger.firstValue() < middles.lastValue()){\n            larger.add(middles.pollLast());\n            middles.add(larger.pollFirst());\n        }\n    }\n    void print(){\n        System.out.println("smaller "+ smaller);\n        System.out.println("middles "+ middles);\n        System.out.println("larger "+ larger);\n        System.out.println();\n    }\n    public int calculateMKAverage() {\n        if(queue.size() < containerSize) return -1;\n        int deno = containerSize - (2 * smaller.getMaxSize());\n        return middles.getSum()/deno;\n    }\n\n}\nclass Node {\n        int val;\n        int index;\n        Node(int val, int index) {\n            this.val = val;\n            this.index = index;\n        }\n        @Override\n        public String toString(){\n            return val +" -> "+index;\n        }\n    }\nclass MultiSet{\n    private int sum;\n    private int maxSize;\n    private TreeSet<Node> set;\n\n    MultiSet(){\n        sum = 0;\n        set = new TreeSet<Node>((first, second) -> {\n            if(first.val == second.val) return first.index - second.index;\n            return first.val - second.val;\n        });\n    }\n    void setMaxSize(int maxSize){\n        this.maxSize = maxSize;\n    }\n    int getMaxSize(){\n        return maxSize;\n    }\n    void clear(){\n        set.clear();\n    }\n    int lastValue(){\n        return set.last().val;\n    }\n    int firstValue(){\n        return set.first().val;\n    }\n    void add(Node node){\n        sum+=node.val;\n        set.add(node);\n    }\n    void remove(Node node){\n        sum-=node.val;\n        set.remove(node);\n    }\n    Node pollFirst(){\n        Node node = set.pollFirst();\n        sum-=node.val;\n        return node;\n    }\n    Node pollLast(){\n        Node node = set.pollLast();\n        sum-=node.val;\n        return node;\n    }\n    int getSum(){\n        return sum;\n    }\n    int size(){\n        return set.size();\n    }\n    boolean contains(Node node){\n        return set.contains(node);\n    }\n\n    @Override\n    public String toString(){\n        return set.toString();\n    }\n}\n```
['Java']