Java TreeMap and Queue
IntuitionSince it needs elements to be in sorted order so that the largest and smallest k elements can be ignored, and there can also be duplicate elements, we
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Since it needs elements to be in sorted order so that the largest and smallest k elements can be ignored, and there can also be duplicate elements, we will use TreeMap.
And in order to remove oldest element when more than m elements are inserted, we use Queue to store the elements.
# Approach
<!-- Describe your approach to solving the problem. -->
While inserting, check if the queue size is already equal to m.
If yes, remove the first element in the Queue, and reduce the count of the element in the treemap, if the count reduces to zero, remove the key altogether.

While calculating average, loop over treemap elements. Following scenarios can occur:
- previous elements count + current element count <= k  : It means this element is not to be added in the sum
- k < previous elements count + current element count <= m - k :
    - If k > previous elements count : Remove k - prev count from current element count to be added. As this count lies in k smallest elements
- previous elements count + current element count > m - k :
    - If k > previous elements count : Remove k - prev count from current element count to be added. As this count lies in k smallest elements
    - Remove (prev count + current element count) - (m - k) from the current element count to be added. As this count lies in k largest elements
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O(m)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(m)

# Code
```java []
class MKAverage {

    Map<Integer, Integer> numCounts;
    Queue<Integer> elements;
    int numElements;
    int m, k;

    public MKAverage(int m, int k) {
        numCounts = new TreeMap<>();
        elements = new LinkedList<>();
        numElements = 0;
        this.m = m;
        this.k = k;
    }
    
    public void addElement(int num) {
        if(numElements == m) {
            int old = elements.poll();
            numCounts.put(old, numCounts.get(old) - 1);
            if(numCounts.get(old) == 0) numCounts.remove(old);
            numElements--;
        }
        elements.add(num);
        numCounts.put(num, numCounts.getOrDefault(num, 0)+1);
        numElements++;
    }
    
    public int calculateMKAverage() {
        if(numElements < m) return -1;
        int freqSum = 0;
        int numSum = 0;
        for(Map.Entry<Integer, Integer> entry: numCounts.entrySet()) {
            int num = entry.getKey();
            int numCount = entry.getValue();
            int count = numCount;
            if(freqSum + numCount > k) {
                if(freqSum + numCount <= m - k){
                    if(k > freqSum) count -= k - freqSum;
                    numSum += count*num;
                } else {
                    if(k > freqSum) count -= k - freqSum;
                    count -= freqSum + numCount - (m - k);
                    numSum += count*num;
                }
            }
            freqSum += numCount;
            if(freqSum >= m - k) break;
        }
        return numSum/(m - (2*k));
    }
}


/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage obj = new MKAverage(m, k);
 * obj.addElement(num);
 * int param_2 = obj.calculateMKAverage();
 */
```
['Java']