Best Java Solution || Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass MKAverage {\n\n    private int m;\n    private int k;\n    private int size = 0;\n    private long sum = 0L;\n\n    private Queue<Integer> q = new ArrayDeque<>(m);\n    private TreeMap<Integer, Integer> left = new TreeMap<>();\n    private TreeMap<Integer, Integer> middle = new TreeMap<>();\n    private TreeMap<Integer, Integer> right = new TreeMap<>();\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n    }\n\n    private void removeOne(TreeMap<Integer, Integer> map, int num) {\n        Integer rmCount = map.get(num);\n        if (rmCount.equals(1)) {\n            map.remove(num);\n        } else {\n            map.put(num, rmCount - 1);\n        }\n    }\n\n    private void edgeFix(TreeMap<Integer, Integer> prev, TreeMap<Integer, Integer> next) {\n        if (next.firstKey() < prev.lastKey()) {\n            Integer nextKey = next.firstKey();\n            Integer nextCount = next.get(nextKey);\n            Integer prevKey = prev.lastKey();\n            Integer prevCount = prev.get(prevKey);\n            if (prevCount.equals(1)) {\n                prev.remove(prevKey);\n            } else {\n                prev.put(prevKey, prevCount - 1);\n            }\n            prev.put(nextKey, prev.getOrDefault(nextKey, 0) + 1);\n            if (nextCount.equals(1)) {\n                next.remove(nextKey);\n            } else {\n                next.put(nextKey, nextCount - 1);\n            }\n            next.put(prevKey, next.getOrDefault(prevKey, 0) + 1);\n            if (prev == middle) {\n                sum = sum - prevKey + nextKey;\n            }\n            if (next == middle) {\n                sum = sum - nextKey + prevKey;\n            }\n        }\n    }\n\n    public void addElement(int num) {\n        q.offer(num);\n        // all full\n        if (size == m) {\n            Integer rm = q.poll();\n            // remove and add the same value, no need to change\n            if (rm == num) {\n                return;\n            }\n            // the position of the value removed\n            boolean removeLeft = false;\n            boolean removeRight = false;\n            TreeMap<Integer, Integer> rmMap = null;\n            if (rm >= middle.firstKey() && rm <= middle.lastKey()) {\n                removeOne(middle, rm);\n                sum = sum - rm;\n            } else if (rm <= left.lastKey()) {\n                removeLeft = true;\n                removeOne(left, rm);\n            } else if (rm >= right.firstKey()) {\n                removeRight = true;\n                removeOne(right, rm);\n            }\n            // insert new value into middle first \n            middle.put(num, middle.getOrDefault(num, 0) + 1);\n            sum = sum + num;\n            // update values\n            if (removeLeft) {\n                Integer moveKey = middle.firstKey();\n                removeOne(middle, moveKey);\n                sum = sum - moveKey;\n                left.put(moveKey, left.getOrDefault(moveKey, 0) + 1);\n                } else if (removeRight) {\n                Integer moveKey = middle.lastKey();\n                removeOne(middle, moveKey);\n                sum = sum - moveKey;\n                right.put(moveKey, right.getOrDefault(moveKey, 0) + 1);\n            }\n            edgeFix(middle, right);\n            edgeFix(left, middle);\n            return;\n        }\n        // if not full\n        // left not full\n        if (size < k) {\n            left.put(num, left.getOrDefault(num, 0) + 1);\n        } else {\n            // left is full\n            Integer maxLeft = left.lastKey();\n            // num is in left\n            if (num < maxLeft) {\n                left.put(num, left.getOrDefault(num, 0) + 1);\n                Integer maxLeftCount = left.get(maxLeft);\n                if (maxLeftCount == 1) {\n                    left.remove(maxLeft);\n                } else {\n                    left.put(maxLeft, maxLeftCount - 1);\n                }\n                num = maxLeft;\n            }\n            // right not full\n            if (size < k + k) {\n                right.put(num, right.getOrDefault(num, 0) + 1);\n            } else {\n                // num is in right\n                Integer minRight = right.firstKey();\n                if (num > minRight) {\n                    right.put(num, right.getOrDefault(num, 0) + 1);\n                    Integer minRightCount = right.get(minRight);\n                    if (minRightCount == 1) {\n                        right.remove(minRight);\n                    } else {\n                        right.put(minRight, minRightCount - 1);\n                    }\n                    num = minRight;\n                }\n                // middle is not full\n                middle.put(num, middle.getOrDefault(num, 0) + 1);\n                sum += num;\n            }\n        }\n        size++;\n    }\n\n    public int calculateMKAverage() {\n        if (size < m) {\n            return -1;\n        }\n        return (int) (sum / (size - k - k));\n    }\n}\n\n\n\n\n\n/*\n\n// this code is correct and T.C = O(logn);\n   but it gives wrong answer for 16/17 cases even my output and the expected output both are same\n\nclass MKAverage {\n\n    ArrayList<Integer> arr;\n    int m;\n    int k;\n    int sum;\n\n    PriorityQueue<Integer> min = new PriorityQueue<>();\n    PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());\n\n\n    public MKAverage(int M, int K) {\n        arr = new ArrayList<>();\n        m=M;\n        k=K;\n        sum=0;\n    }\n    \n    public void addElement(int num) {\n        if(arr.size()<m){\n            arr.add(num);\n            sum+=num;\n            min.add(num);\n            max.add(num);\n        } \n        else{\n            int a = arr.get(0);\n            sum = sum-a;\n            arr.remove(0);\n            arr.add(arr.size(),num);\n            sum=sum+num;\n            min.remove(a);\n            max.remove(a);\n            min.add(num);\n            max.add(num);\n        }\n        \n    }\n    \n    public int calculateMKAverage() {\n\n        if(arr.size()<m) return -1;\n        \n\n        int a = min.peek();\n        int b = max.peek();\n        return (sum-a-b)/(m-2);\n    }\n}\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * MKAverage obj = new MKAverage(m, k);\n * obj.addElement(num);\n * int param_2 = obj.calculateMKAverage();\n */\n```
['Java']