1825. Finding MK Average LeetCode Solution
In this guide, you will get 1825. Finding MK Average LeetCode Solution with the best time and space complexity. The solution to Finding MK Average problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Finding MK Average solution in C++
- Finding MK Average solution in Java
- Finding MK Average solution in Python
- Additional Resources
Problem Statement of Finding MK Average
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:
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.
Remove the smallest k elements and the largest k elements from the container.
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.
Complexity Analysis
- Time Complexity: O(n\log n)
- Space Complexity: O(n)
1825. Finding MK Average LeetCode Solution in C++
class MKAverage {
public:
MKAverage(int m, int k) : m(m), k(k) {}
void addElement(int num) {
q.push(num);
add(mid, num);
midSum += num;
if (q.size() > m) {
const int removed = q.front();
q.pop();
if (top.contains(removed)) {
remove(top, removed);
--topSize;
} else if (mid.contains(removed)) {
remove(mid, removed);
midSum -= removed;
} else {
remove(bot, removed);
--botSize;
}
}
// Move item(s) from `mid` to `top` to fill k slots.
while (!mid.empty() && topSize < k) {
midSum -= mid.rbegin()->first;
add(top, remove(mid, mid.rbegin()->first));
++topSize;
}
// Rebalance `mid` and `top`.
while (!mid.empty() && mid.rbegin()->first > top.begin()->first) {
midSum -= mid.rbegin()->first;
midSum += top.begin()->first;
add(top, remove(mid, mid.rbegin()->first));
add(mid, remove(top, top.begin()->first));
}
// Move item(s) from `mid` to `bot` to fill k slots.
while (!mid.empty() && botSize < k) {
midSum -= mid.begin()->first;
add(bot, remove(mid, mid.begin()->first));
++botSize;
}
// Move item(s) from `mid` to `bot` to fill k slots.
while (!mid.empty() && mid.begin()->first < bot.rbegin()->first) {
midSum -= mid.begin()->first;
midSum += bot.rbegin()->first;
add(bot, remove(mid, mid.begin()->first));
add(mid, remove(bot, bot.rbegin()->first));
}
}
int calculateMKAverage() {
return q.size() == m ? midSum / (m - 2 * k) : -1;
}
private:
const int m;
const int k;
queue<int> q;
map<int, int> top;
map<int, int> mid;
map<int, int> bot;
int topSize = 0;
int botSize = 0;
long midSum = 0;
void add(map<int, int>& map, int num) {
++map[num];
}
int remove(map<int, int>& map, int num) {
if (--map[num] == 0)
map.erase(num);
return num;
}
};
/* code provided by PROGIEZ */1825. Finding MK Average LeetCode Solution in Java
class MKAverage {
public MKAverage(int m, int k) {
this.m = m;
this.k = k;
}
public void addElement(int num) {
q.offer(num);
add(mid, num);
midSum += num;
if (q.size() > m) {
final int removed = q.poll();
if (top.containsKey(removed)) {
remove(top, removed);
--topSize;
} else if (mid.containsKey(removed)) {
remove(mid, removed);
midSum -= removed;
} else {
remove(bot, removed);
--botSize;
}
}
// Move item(s) from `mid` to `top` to fill k slots.
while (!mid.isEmpty() && topSize < k) {
midSum -= mid.lastKey();
add(top, remove(mid, mid.lastKey()));
++topSize;
}
// Rebalance `mid` and `top`.
while (!mid.isEmpty() && mid.lastKey() > top.firstKey()) {
midSum -= mid.lastKey();
midSum += top.firstKey();
add(top, remove(mid, mid.lastKey()));
add(mid, remove(top, top.firstKey()));
}
// Move item(s) from `mid` to `bot` to fill k slots.
while (!mid.isEmpty() && botSize < k) {
midSum -= mid.firstKey();
add(bot, remove(mid, mid.firstKey()));
++botSize;
}
// Rebalance mid and bot
while (!mid.isEmpty() && mid.firstKey() < bot.lastKey()) {
midSum -= mid.firstKey();
midSum += bot.lastKey();
add(bot, remove(mid, mid.firstKey()));
add(mid, remove(bot, bot.lastKey()));
}
}
public int calculateMKAverage() {
return q.size() == m ? (int) (midSum / (m - 2 * k)) : -1;
}
private final int m;
private final int k;
private Queue<Integer> q = new ArrayDeque<>();
private TreeMap<Integer, Integer> top = new TreeMap<>();
private TreeMap<Integer, Integer> mid = new TreeMap<>();
private TreeMap<Integer, Integer> bot = new TreeMap<>();
private int topSize = 0;
private int botSize = 0;
private long midSum = 0;
private void add(TreeMap<Integer, Integer> map, int num) {
map.merge(num, 1, Integer::sum);
}
private int remove(TreeMap<Integer, Integer> map, int num) {
map.put(num, map.get(num) - 1);
if (map.get(num) == 0)
map.remove(num);
return num;
}
}
// code provided by PROGIEZ1825. Finding MK Average LeetCode Solution in Python
struct MyMap {
map<int, int> map;
int size = 0;
long sum = 0;
};
class MKAverage {
public:
MKAverage(int m, int k) : m(m), k(k), kMidSize(m - 2 * k) {}
void addElement(int num) {
q.push(num);
add(num);
if (q.size() > m) {
const int removed = q.front();
q.pop();
remove(removed);
}
}
int calculateMKAverage() {
return q.size() == m ? mid.sum / kMidSize : -1;
}
private:
const int m;
const int k;
const int kMidSize;
queue<int> q;
MyMap top;
MyMap mid;
MyMap bot;
void add(int num) {
add(bot, num);
if (bot.size > k)
add(mid, remove(bot, bot.map.rbegin()->first));
if (mid.size > kMidSize)
add(top, remove(mid, mid.map.rbegin()->first));
}
void remove(int num) {
if (bot.map.contains(num))
remove(bot, num);
else if (mid.map.contains(num))
remove(mid, num);
else
remove(top, num);
if (bot.size < k)
add(bot, remove(mid, mid.map.begin()->first));
if (mid.size < kMidSize)
add(mid, remove(top, top.map.begin()->first));
}
void add(MyMap& m, int num) {
++m.map[num];
++m.size;
m.sum += num;
}
int remove(MyMap& m, int num) {
if (--m.map[num] == 0)
m.map.erase(num);
--m.size;
m.sum -= num;
return num;
}
};
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.
Similar:
