Approach
Breadth-first search
For Finding MK Average, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 71 lines of C++ from the credited upstream file 1825-2.cpp.
- The implementation visibly relies on ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1struct MyMap {2 map<int, int> map;3 int size = 0;4 long sum = 0;5};6 7class MKAverage {8 public:9 MKAverage(int m, int k) : m(m), k(k), kMidSize(m - 2 * k) {}10 11 void addElement(int num) {12 q.push(num);13 add(num);14 15 if (q.size() > m) {16 const int removed = q.front();17 q.pop();18 remove(removed);19 }20 }21 22 int calculateMKAverage() {23 return q.size() == m ? mid.sum / kMidSize : -1;24 }25 26 private:27 const int m;28 const int k;29 const int kMidSize;30 queue<int> q;31 MyMap top;32 MyMap mid;33 MyMap bot;34 35 void add(int num) {36 add(bot, num);37 if (bot.size > k)38 add(mid, remove(bot, bot.map.rbegin()->first));39 if (mid.size > kMidSize)40 add(top, remove(mid, mid.map.rbegin()->first));41 }42 43 void remove(int num) {44 if (bot.map.contains(num))45 remove(bot, num);46 else if (mid.map.contains(num))47 remove(mid, num);48 else49 remove(top, num);50 51 if (bot.size < k)52 add(bot, remove(mid, mid.map.begin()->first));53 if (mid.size < kMidSize)54 add(mid, remove(top, top.map.begin()->first));55 }56 57 void add(MyMap& m, int num) {58 ++m.map[num];59 ++m.size;60 m.sum += num;61 }62 63 int remove(MyMap& m, int num) {64 if (--m.map[num] == 0)65 m.map.erase(num);66 --m.size;67 m.sum -= num;68 return num;69 }70};71