In many problems, where we are given a set of elements such that we can divide them into two parts. To solve the problem, we are interested in knowing the smallest element in one part and the biggest element in the other part. This pattern is an efficient approach to solve such problems.

This pattern uses two Heaps to solve these problems;

A Min Heap to find the smallest element and a Max Heap to find the biggest element.

Use cases

Find median in data stream

1. Define which heap is going to be bigger (max heap in this case).
2. If number of elements in both heaps is equal → even elements total → take two middle guys and / 2
3. If not equal take a number from biggest heap.

PriorityQueue<Integer> maxHeap; //containing first half of numbers
PriorityQueue<Integer> minHeap; //containing second half of numbers

public MedianFinder2() {
    maxHeap = new PriorityQueue<>((a, b) -> b - a);
    minHeap = new PriorityQueue<>((a, b) -> a - b);
}

public void insertNum(int num) {
    if (maxHeap.isEmpty() || maxHeap.peek() >= num)
        maxHeap.add(num);
    else
        minHeap.add(num);

    // either both the heaps will have equal number of elements or max-heap will have one
    // more element than the min-heap
    if (maxHeap.size() > minHeap.size() + 1)
        minHeap.add(maxHeap.poll());
    else if (maxHeap.size() < minHeap.size())
        maxHeap.add(minHeap.poll());
}

public double findMedian() {
    if (maxHeap.size() == minHeap.size()) {
        // we have even number of elements, take the average of middle two elements
        return maxHeap.peek() / 2.0 + minHeap.peek() / 2.0;
    }
    // because max-heap will have one more element than the min-heap
    return maxHeap.peek();
}

The same pattern:

Sliding Window Median

Or we can use two heaps to find cases for different inputs

Find Right Interval

1. Ends to maxHeap and starts to different maxHeap.
2. Pick up end value from maxHeap and and try to find corresponding start value in minHeap.
3. Traverse starts till condition is satisfied and put back.

public int[] findRightInterval(int[][] intervals) {
   
    PriorityQueue<Integer> maxEndHeap =
            new PriorityQueue<>((i1, i2) -> (intervals[i2][1] - intervals[i1][1]));
    PriorityQueue<Integer> maxStartHeap =
            new PriorityQueue<>((i1, i2) -> (intervals[i2][0] - intervals[i1][0]));
    for (int i = 0; i < intervals.length; i++) {
        maxEndHeap.add(i);
        maxStartHeap.add(i);
    }
    int n = intervals.length;
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        int topEnd = maxEndHeap.poll();
        result[topEnd] = -1; // def case
        if (intervals[maxStartHeap.peek()][0] >= intervals[topEnd][1]) {
            int topStart = maxStartHeap.peek();
            while (!maxStartHeap.isEmpty() && intervals[maxStartHeap.peek()][0] >= intervals[topEnd][1]) {
                topStart = maxStartHeap.poll();
            }
            result[topEnd] = topStart;
            maxStartHeap.add(topStart);
        }
    }
    return result;
}

The same pattern:

IPO