295. Find Median from Data Stream – Leetcode Solutions

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

import heapq

class MedianFinder:

    def __init__(self):
        # Max-Heap for the lower half (we negate the values to simulate a max-heap using Python's min-heap)
        self.max_heap = []
        # Min-Heap for the upper half
        self.min_heap = []

    def addNum(self, num: int) -> None:
        # Add to max-heap (smaller half). We negate the value to simulate a max-heap.
        heapq.heappush(self.max_heap, -num)
        
        # Ensure the smallest of the larger half (min-heap) is always greater than the largest of the smaller half (max-heap).
        if self.max_heap and self.min_heap and (-self.max_heap[0] > self.min_heap[0]):
            # Move the largest element from the max-heap to the min-heap to maintain order
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        
        # Balance the heaps: max-heap can only have at most one more element than min-heap
        if len(self.max_heap) > len(self.min_heap) + 1:
            # Move the largest element of max-heap to min-heap
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        elif len(self.min_heap) > len(self.max_heap):
            # Move the smallest element of min-heap to max-heap
            val = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -val)

    def findMedian(self) -> float:
        # If max-heap has more elements, the median is the root of max-heap
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        # If both heaps have the same number of elements, the median is the average of the roots of both heaps
        return (-self.max_heap[0] + self.min_heap[0]) / 2.0

#include <queue>

class MedianFinder {
public:
    // Constructor: Initialize the two heaps
    MedianFinder() {
        // No special initialization required
    }
    
    // Add a new number to the data structure
    void addNum(int num) {
        // Add the number to the max-heap first
        max_heap.push(num);
        
        // Balance step 1: Ensure the max-heap doesn't have elements greater than the min-heap
        min_heap.push(max_heap.top());
        max_heap.pop();
        
        // Balance step 2: Ensure the max-heap has at most one more element than the min-heap
        if (max_heap.size() < min_heap.size()) {
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
    }
    
    // Find the median of all the numbers added so far
    double findMedian() {
        // If the max-heap has more elements, return the top of the max-heap
        if (max_heap.size() > min_heap.size()) {
            return max_heap.top();
        }
        
        // Otherwise, return the average of the tops of both heaps
        return (max_heap.top() + min_heap.top()) / 2.0;
    }
    
private:
    // Max-Heap to store the smaller half of the numbers (inverted values for a max-heap behavior)
    std::priority_queue<int> max_heap;
    
    // Min-Heap to store the larger half of the numbers
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
};

var MedianFinder = function() {
    // Initialize two heaps (max heap for the left half, min heap for the right half)
    // Using two heaps allows us to maintain the left half with a max heap and right half with a min heap.
    
    this.small = new MaxPriorityQueue();  // Max heap for the smaller half of numbers
    this.large = new MinPriorityQueue();  // Min heap for the larger half of numbers
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    // Add the new number into the max heap (small).
    // Push the element to the small heap, and then we balance the heaps by moving the largest element of small to large.
    
    this.small.enqueue(num);
    
    // Balance the heaps: Ensure that every element in `small` is less than or equal to the elements in `large`.
    // If the root of small (largest of small heap) is greater than the root of large, transfer the root.
    if (this.small.size() > 0 && this.large.size() > 0 && this.small.front().element > this.large.front().element) {
        let maxFromSmall = this.small.dequeue().element;
        this.large.enqueue(maxFromSmall);
    }
    
    // Ensure the heaps are balanced in size
    // We are trying to maintain that `small` heap may have at most 1 extra element than the `large` heap.
    if (this.small.size() > this.large.size() + 1) {
        this.large.enqueue(this.small.dequeue().element);
    } else if (this.large.size() > this.small.size()) {
        this.small.enqueue(this.large.dequeue().element);
    }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    // If the heaps are of different sizes, the median is the root of the heap with the extra element.
    if (this.small.size() > this.large.size()) {
        return this.small.front().element;
    }
    
    // If both heaps are balanced (same size), the median is the average of both heap roots.
    return (this.small.front().element + this.large.front().element) / 2;
};

import java.util.PriorityQueue;

class MedianFinder {

    // Declare two heaps: 
    // A max heap to store the smaller half of the numbers.
    // A min heap to store the larger half of the numbers.
    private PriorityQueue<Integer> small;  // Max heap
    private PriorityQueue<Integer> large;  // Min heap

    // Constructor to initialize the MedianFinder object
    public MedianFinder() {
        // Max heap (in Java, PriorityQueue is a min-heap by default, so we need to invert the order for the max heap).
        small = new PriorityQueue<>((a, b) -> b - a);
        // Min heap (stores the larger half of numbers).
        large = new PriorityQueue<>();
    }

    // Method to add a number to the data structure.
    public void addNum(int num) {
        // Add number to the max heap first (small).
        small.offer(num);
        
        // Ensure the elements in `small` are less than or equal to the elements in `large`.
        // Move the largest element from `small` to `large` to maintain order.
        if (!small.isEmpty() && !large.isEmpty() && small.peek() > large.peek()) {
            large.offer(small.poll());
        }
        
        // Balance the heaps to maintain size property: 
        // Either both heaps should be the same size or `small` can have one more element than `large`.
        if (small.size() > large.size() + 1) {
            large.offer(small.poll());
        } else if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }

    // Method to find and return the median of the current list of numbers.
    public double findMedian() {
        // If `small` has more elements, the median is the top of the max heap (small).
        if (small.size() > large.size()) {
            return small.peek();
        }
        
        // If both heaps are the same size, the median is the average of the tops of the two heaps.
        return (small.peek() + large.peek()) / 2.0;
    }
}