Solution: Min Heap and Max Heap

This problem can be efficiently solved using two heaps: a min-heap and a max-heap. The min-heap (minQ) will store the larger half of the numbers added, and the max-heap (maxQ) will store the smaller half. This setup allows us to quickly find the median.

Algorithm:

1. Initialization: Create an empty min-heap (minQ) and an empty max-heap (maxQ).

2. addNum(num):

   • Add the new number num to the max-heap (maxQ).
   • If the size of maxQ becomes greater than the size of minQ by more than 1, move the largest element from maxQ to minQ.
   • If the size of minQ becomes greater than the size of maxQ, move the smallest element from minQ to maxQ. This ensures that the heaps remain balanced, with their sizes differing by at most 1.

3. findMedian():

   • If the sizes of minQ and maxQ are equal, the median is the average of the top elements of both heaps.
   • If the size of minQ is greater than the size of maxQ, the median is the top element of minQ.

Time Complexity:

• addNum(num): O(log n), where n is the number of elements added so far. Heap operations (insertion and deletion) take logarithmic time.
• findMedian(): O(1). Accessing the top element of a heap is a constant-time operation.

Space Complexity: O(n), as we store all the numbers added in the heaps.

Code Examples:

The code examples below demonstrate the implementation in various programming languages. Note that the specific heap implementation might vary depending on the language's standard library (e.g., PriorityQueue in Java, heapq in Python).

Python:

import heapq
 
class MedianFinder:
    def __init__(self):
        self.min_heap = []  # Min-heap to store larger half
        self.max_heap = []  # Max-heap to store smaller half
 
    def addNum(self, num: int) -> None:
        heapq.heappush(self.max_heap, -num)  # Use negative for max-heap
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        if len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
 
    def findMedian(self) -> float:
        if len(self.min_heap) == len(self.max_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return -self.max_heap[0]

Java:

import java.util.PriorityQueue;
import java.util.Collections;
 
class MedianFinder {
    private PriorityQueue<Integer> minHeap;
    private PriorityQueue<Integer> maxHeap;
 
    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    }
 
    public void addNum(int num) {
        maxHeap.offer(num);
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        }
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
 
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (double)(maxHeap.peek() + minHeap.peek()) / 2;
        } else {
            return (double)maxHeap.peek();
        }
    }
}

(Other languages would follow a similar structure, using their respective heap implementations.)

This approach provides an efficient and elegant solution to the problem of finding the median from a data stream. The use of two heaps keeps the data balanced and allows for logarithmic time complexity for addNum operations.