Find Median from Data Stream hard

Problem Statement

Design a data structure that supports the following two operations:

• void addNum(int num): Add a number to the data structure.
• double findMedian(): Return the median of the data structure.

The median is the middle value in an ordered integer list. If the size of the data structure is even, the median is the average of the two middle values.

Example 1:

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (1 + 2) / 2 = 1.5
medianFinder.addNum(3);    // arr = [1, 2, 3]
medianFinder.findMedian(); // return 2

Example 2:

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(5);    // arr = [1, 5]
medianFinder.addNum(2);    // arr = [1, 2, 5]
medianFinder.findMedian(); // return 2

Steps and Explanation

This problem is efficiently solved using two heaps: a max-heap to store the smaller half of the elements and a min-heap to store the larger half. This approach maintains a balanced structure, allowing for O(log n) time complexity for both addNum and findMedian operations.

1. Data Structures: We use two heaps:

   • maxHeap: A max-heap stores the smaller half of the numbers.
   • minHeap: A min-heap stores the larger half of the numbers.

2. addNum(int num):

   • Add the number to the appropriate heap: If the number is smaller than the top of the minHeap (the smallest of the larger half), add it to maxHeap. Otherwise, add it to minHeap.
   • Balance the heaps: Ensure that the difference in size between the heaps is at most 1. If one heap has two more elements than the other, move the top element from the larger heap to the smaller heap.

3. findMedian():

   • If the total number of elements is odd, the median is the top of the larger heap.
   • If the total number of elements is even, the median is the average of the top elements of both heaps.

Code

using System;
using System.Collections.Generic;

public class MedianFinder {
    private PriorityQueue<int, int> maxHeap; // Smaller half
    private PriorityQueue<int, int> minHeap; // Larger half

    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x))); // Max heap
        minHeap = new PriorityQueue<int, int>(); // Min heap
    }

    public void AddNum(int num) {
        if (maxHeap.Count == 0 || num <= maxHeap.Peek()) {
            maxHeap.Enqueue(num, num);
        } else {
            minHeap.Enqueue(num, num);
        }

        // Balance the heaps
        if (maxHeap.Count > minHeap.Count + 1) {
            minHeap.Enqueue(maxHeap.Dequeue(), maxHeap.Dequeue());
        } else if (minHeap.Count > maxHeap.Count + 1) {
            maxHeap.Enqueue(minHeap.Dequeue(), minHeap.Dequeue());
        }
    }

    public double FindMedian() {
        if (maxHeap.Count == minHeap.Count) {
            return (maxHeap.Peek() + minHeap.Peek()) / 2.0;
        } else if (maxHeap.Count > minHeap.Count) {
            return maxHeap.Peek();
        } else {
            return minHeap.Peek();
        }
    }
}

Complexity

• Time Complexity:

  • addNum: O(log n) due to heap operations.
  • findMedian: O(1) as it only accesses the top elements of the heaps.

• Space Complexity: O(n) to store the elements in the heaps.

Note: This C# code utilizes the PriorityQueue class which is available from .NET 6 and later. If using an older version, you'll need to implement your own heap data structure or use a third-party library. Remember to add using System.Collections.Generic; at the beginning of your file.