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 Java from the credited upstream file 1825-2.java.
- 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.
1class MyMap {2 public TreeMap<Integer, Integer> map = new TreeMap<>();3 public int size = 0;4 public long sum = 0;5}6 7class MKAverage {8 public MKAverage(int m, int k) {9 this.m = m;10 this.k = k;11 this.MID_SIZE = m - 2 * k;12 }13 14 public void addElement(int num) {15 q.offer(num);16 add(num);17 18 if (q.size() > m)19 remove(q.poll());20 }21 22 public int calculateMKAverage() {23 return q.size() == m ? (int) (mid.sum / MID_SIZE) : -1;24 }25 26 private final int m;27 private final int k;28 private final int MID_SIZE;29 private Queue<Integer> q = new ArrayDeque<>();30 private MyMap bot = new MyMap();31 private MyMap mid = new MyMap();32 private MyMap top = new MyMap();33 34 private void add(int num) {35 add(bot, num);36 if (bot.size > k)37 add(mid, remove(bot, bot.map.lastKey()));38 if (mid.size > MID_SIZE)39 add(top, remove(mid, mid.map.lastKey()));40 }41 42 private void remove(int num) {43 if (bot.map.containsKey(num))44 remove(bot, num);45 else if (mid.map.containsKey(num))46 remove(mid, num);47 else48 remove(top, num);49 50 if (bot.size < k)51 add(bot, remove(mid, mid.map.firstKey()));52 if (mid.size < MID_SIZE)53 add(mid, remove(top, top.map.firstKey()));54 }55 56 private void add(MyMap m, int num) {57 m.map.merge(num, 1, Integer::sum);58 ++m.size;59 m.sum += num;60 }61 62 private int remove(MyMap m, int num) {63 m.map.merge(num, -1, Integer::sum);64 if (m.map.get(num) == 0)65 m.map.remove(num);66 --m.size;67 m.sum -= num;68 return num;69 }70}71