Skip to content

1953. Finding Mk Average

Difficulty: Hard

LeetCode Problem View on GitHub

1953. Finding MK Average

Hard

You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:

  1. If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.
  2. Remove the smallest k elements and the largest k elements from the container.
  3. Calculate the average value for the rest of the elements rounded down to the nearest integer.

Implement the MKAverage class:

  • MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.
  • void addElement(int num) Inserts a new element num into the stream.
  • int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.

 

Example 1:

Input
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]

Explanation
MKAverage obj = new MKAverage(3, 1); 
obj.addElement(3);        // current elements are [3]
obj.addElement(1);        // current elements are [3,1]
obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist.
obj.addElement(10);       // current elements are [3,1,10]
obj.calculateMKAverage(); // The last 3 elements are [3,1,10].
                          // After removing smallest and largest 1 element the container will be [3].
                          // The average of [3] equals 3/1 = 3, return 3
obj.addElement(5);        // current elements are [3,1,10,5]
obj.addElement(5);        // current elements are [3,1,10,5,5]
obj.addElement(5);        // current elements are [3,1,10,5,5,5]
obj.calculateMKAverage(); // The last 3 elements are [5,5,5].
                          // After removing smallest and largest 1 element the container will be [5].
                          // The average of [5] equals 5/1 = 5, return 5

 

Constraints:

  • 3 <= m <= 105
  • 1 <= k*2 < m
  • 1 <= num <= 105
  • At most 105 calls will be made to addElement and calculateMKAverage.

Solution

class MKAverage {
    private TreeMap<Integer, Integer> map;
    private Deque<Integer> dq;
    int m, k, sum;
    public MKAverage(int m, int k) {
        map = new TreeMap<>();
        dq = new ArrayDeque<>();
        this.m = m;
        this.k = k;
        sum = 0;
    }
    public void addElement(int num) {
        dq.addLast(num);
        sum += num;
        map.put(num, map.getOrDefault(num, 0) + 1);
        if (dq.size() > m) {
            int to_remove = dq.pollFirst();
            sum -= to_remove;
            map.put(to_remove, map.getOrDefault(to_remove, 0) -1);
            if (map.getOrDefault(to_remove, 0) == 0) map.remove(to_remove);
        }
    }
    public int calculateMKAverage() {
        if (dq.size() < m) return -1;
        int first_smallest_sum = 0, first_largest_sum = 0, count = 0, current_key = map.firstKey();
        while (count < k) {
            if (map.get(current_key) + count <= k) {
                count += map.get(current_key);
                first_smallest_sum += map.get(current_key) * current_key;
                current_key = map.higherKey(current_key);
            }
            else {
                first_smallest_sum += current_key * (k - count);
                break;
            }
        }
        current_key = map.lastKey();
        count = 0;
        while (count < k) {
            if (map.get(current_key) + count <= k) {
                first_largest_sum += map.get(current_key) * current_key;
                count += map.get(current_key);
                current_key = map.lowerKey(current_key);
            }
            else {
                first_largest_sum += current_key * (k - count);
                break;
            }
        }
        int res = sum - first_smallest_sum - first_largest_sum;
        return res / (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();
 */

Complexity Analysis

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

Approach

Detailed explanation of the approach will be added here