Two Heaps

The Two Heaps coding pattern is a technique used to efficiently solve problems that involve managing a data stream or dynamic set of elements while maintaining certain properties. It utilizes two heaps, usually a max-heap and a min-heap, to achieve these goals.

Here’s an explanation of the Two Heaps pattern:

1. Two Heaps: Maintain two heaps: a max-heap to store elements that are smaller than the median, and a min-heap to store elements that are larger than the median.
2. Balancing: Ensure that the size of both heaps is either equal or differs by at most one element. This balancing ensures that the median can be easily found in constant time.
3. Insertion: When inserting an element, compare it with the current median. If it’s smaller, insert it into the max-heap; if it’s larger, insert it into the min-heap. After insertion, ensure the balancing condition.
4. Finding Median: The median can be directly obtained from the root nodes of the max-heap and min-heap. If the heaps are balanced, the average of these two values is the median.

The Two Heaps pattern is especially useful for solving problems that require efficient tracking of the median or other percentile values as new elements are added or removed from the data stream.

A common application of the Two Heaps pattern is in finding the median of a continuous stream of numbers. By maintaining a max-heap for smaller elements and a min-heap for larger elements, you can always find the median efficiently. This approach avoids the need to sort the entire list of elements every time a new element is added, resulting in a time complexity of O(log n) for insertion and retrieval of the median.

• Find Median from Data Stream
  Write program to Find Median from Data Stream
• Sliding Window Median
  Given an array of integers nums and an integer k, you need to find the median of each window of size k moving from left to right in the array. The window slides by one position each time.
• IPO Problem
  You are given k projects, each with a capital value and a profit value. You are also given an initial capital. The i-th project requires capital[i] capital to start, and the profit of the i-th project is profits[i]. Once a project is selected, you can invest its capital and start it to get the profit. After each project is finished, you can choose to reinvest the profit back into one of the available projects.
• Find Right Interval
  Given a list of intervals intervals, where intervals[i] = [start_i, end_i], for each interval i, find the index of the interval j such that start_j is the smallest possible value that is equal to or greater than end_i. If there is no such interval j, the output should be -1.