LeetCode 1825: Finding MK Average
Problem Description
Explanation:
To solve this problem, we can use a combination of a queue and a multiset (or two priority queues) to maintain the stream of elements and calculate the MKAverage as required. Here is the basic idea:
- Initialize the MKAverage object with the given values of m and k.
- Maintain a queue of size m to store the last m elements of the stream.
- Maintain a multiset (or two priority queues) to efficiently get the smallest k elements and largest k elements.
- When adding a new element, update the queue and the multiset accordingly.
- When calculating the MKAverage, if the size of the stream is less than m, return -1. Otherwise, calculate the average of the remaining elements after removing the smallest k and largest k elements.
Time Complexity:
- Adding an element: O(log m) to update the multiset.
- Calculating the MKAverage: O(k log m) to remove smallest and largest k elements.
Space Complexity:
- O(m) for the queue to store the last m elements.
- O(m) for the multiset storing the last m elements.
:
Solutions
import java.util.*;
class MKAverage {
int m, k;
Queue<Integer> queue;
TreeSet<Integer> small, large;
long sum;
public MKAverage(int m, int k) {
this.m = m;
this.k = k;
queue = new LinkedList<>();
small = new TreeSet<>();
large = new TreeSet<>();
sum = 0;
}
public void addElement(int num) {
if (queue.size() == m) {
int old = queue.poll();
if (!small.remove(old)) {
large.remove(old);
sum -= old;
}
}
queue.offer(num);
small.add(num);
large.add(queue.peek());
large.add(queue.peek());
sum += num;
if (queue.size() == m) {
while (small.size() > k) {
sum -= small.first();
large.add(small.first());
small.pollFirst();
}
while (large.size() > k) {
sum -= large.last();
small.add(large.last());
large.pollLast();
}
}
}
public int calculateMKAverage() {
return queue.size() < m ? -1 : (int) (sum / (m - 2 * k));
}
}Loading editor...