Find Median from Data Stream

LeetCode 295 | Difficulty: Hard

Hard

Problem Description

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

- For example, for `arr = [2,3,4]`, the median is `3`.

- For example, for `arr = [2,3]`, the median is `(2 + 3) / 2 = 2.5`.

Implement the MedianFinder class:

- `MedianFinder()` initializes the `MedianFinder` object.

- `void addNum(int num)` adds the integer `num` from the data stream to the data structure.

- `double findMedian()` returns the median of all elements so far. Answers within `10^-5` of the actual answer will be accepted.

Example 1:

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

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

Constraints:

- `-10^5 <= num <= 10^5`

- There will be at least one element in the data structure before calling `findMedian`.

- At most `5 * 10^4` calls will be made to `addNum` and `findMedian`.

Follow up:

- If all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?

- If `99%` of all integer numbers from the stream are in the range `[0, 100]`, how would you optimize your solution?

Topics: Two Pointers, Design, Sorting, Heap (Priority Queue), Data Stream

---

Approach

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

---

Solutions

Solution 1: C# (Best: 1377 ms)

Metric	Value
Runtime	1377 ms
Memory	85.9 MB
Date	2022-02-06

Solution

public class MedianFinder {

    PriorityQueue<int> left;//= new PriorityQueue<int>(Comparer<int>.Create((x,y)=>y.CompareTo(x)));
    PriorityQueue<int> right;// = new PriorityQueue<int>();

    public MedianFinder()
    {
        left = new PriorityQueue<int>(Comparer<int>.Create((x,y)=>y.CompareTo(x)));
        right = new PriorityQueue<int>();
    }

    public void AddNum(int num)
    {
        if(left.size == 0 || left.Peek()>num) left.Enqueue(num);
        else right.Enqueue(num);
        
        if(left.size > right.size+1)
        {
            right.Enqueue(left.Dequeue());
        }
        else if(left.size+1<right.size)
        {
            left.Enqueue(right.Dequeue());
        }
    }

    public double FindMedian()
    {
        if(left.size == right.size) return left.size == 0 ? 0 : ((left.Peek()+right.Peek())/2.0);
        else return (left.size > right.size) ? left.Peek() : right.Peek();
    }
}

public class PriorityQueue<T> where T : IComparable<T>
{
    private SortedDictionary<T, int> data;
    public int size = 0;
    private readonly int? capacity;

    public PriorityQueue(int? capacity = null)
    {
        this.data = new SortedDictionary<T, int>();
        this.capacity = capacity;
    }

    public PriorityQueue(IComparer<T> comparer, int? capacity=null)
    {
        this.data = new SortedDictionary<T, int>(comparer);
        this.capacity = capacity;
    }

    public void Enqueue(T item)
    {
        if(capacity.HasValue && capacity==size) Dequeue();
        if(data.ContainsKey(item))
        {
            data[item]++;
        }
        else
        {
            data.Add(item, 1);
        }
        size++;
    }

    public T Dequeue()
    {
        var front = data.First();
        if(front.Value == 1) data.Remove(front.Key);
        else data[front.Key]--;
        size--;
        return front.Key;
    }

    public T Peek()
    {
        return data.First().Key;
    }

    public int Count()
    {
        return size;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.AddNum(num);
 * double param_2 = obj.FindMedian();
 */

📜 1 more C# submission(s)

Submission (2022-02-06) — 1655 ms, 89.6 MB

public class MedianFinder {

    PriorityQueue<int> left;
    PriorityQueue<int> right;

    public MedianFinder()
    {
        left = new PriorityQueue<int>(Comparer<int>.Create((x,y)=>y.CompareTo(x)));
        right = new PriorityQueue<int>();
    }

    public void AddNum(int num)
    {
        if(left.size == 0 || left.Peek()>num) left.Enqueue(num);
        else right.Enqueue(num);
        
        if(left.size > right.size+1)
        {
            right.Enqueue(left.Dequeue());
        }
        else if(left.size+1<right.size)
        {
            left.Enqueue(right.Dequeue());
        }
    }

    public double FindMedian()
    {
        if(left.size == right.size) return left.size == 0 ? 0 : ((left.Peek()+right.Peek())/2.0);
        else return (left.size > right.size) ? left.Peek() : right.Peek();
    }
}

public class PriorityQueue<T> where T : IComparable<T>
{
    private SortedDictionary<T, int> data;
    public int size = 0;
    private readonly int? capacity;

    public PriorityQueue(int? capacity = null)
    {
        this.data = new SortedDictionary<T, int>();
        this.capacity = capacity;
    }

    public PriorityQueue(IComparer<T> comparer, int? capacity=null)
    {
        this.data = new SortedDictionary<T, int>(comparer);
        this.capacity = capacity;
    }

    public void Enqueue(T item)
    {
        if(capacity.HasValue && capacity==size){ Dequeue(); size--; }
        if(data.ContainsKey(item))
        {
            data[item]++;
        }
        else
        {
            data.Add(item, 1);
        }
        size++;
    }

    public T Dequeue()
    {
        var front = data.First();
        if(front.Value == 1) data.Remove(front.Key);
        else data[front.Key]--;
        size--;
        return front.Key;
    }

    public T Peek()
    {
        return data.First().Key;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.AddNum(num);
 * double param_2 = obj.FindMedian();
 */

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Clarify the expected time complexity for each operation before choosing data structures.