Lining up people by height into two rooms, short and tall, keeping the rooms balanced: the median is at the door between them.
Clues that point here
→ Running median
→ Median of a sliding window
→ Balance two groups
Not this pattern when
✕ You need any percentile other than the middle (use an order-statistic structure)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Two Heaps · template
PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
PriorityQueue<Integer> high = new PriorityQueue<>(); // min-heap
void add(int x) {
low.offer(x);
high.offer(low.poll()); // keep every low <= every high
if (high.size() > low.size()) low.offer(high.poll()); // low may hold one extra
}
double median() {
return low.size() > high.size() ? low.peek() : (low.peek() + high.peek()) / 2.0;
}