295. Find Median from Data Stream

Here is my practice sharing.

It is most challenging problem to solve since the optimal solution is to use two data structure, one is minimum heap, and the other one is maximum heap. I was asked to work on the algorithm in phone screen in March 2017.

It is time for me to review the algorithm again.

How to design minimum heap and maximum heap using C#?

Using C# SortedSet, and also define Comparer.

One tip to make median calcuation easy

It is a good idea to make minimum heap size is bigger than maximum heap size by 1 if total length is is odd.

public class MedianFinder {

    /** initialize your data structure here. */
    public MedianFinder() {
        
    }
    
    private int counter = 0;

        private SortedSet<int[]> setLow = new SortedSet<int[]>(
            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));

        private SortedSet<int[]> setHigh = new SortedSet<int[]>(
            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
            
    public void AddNum(int num) {
        var newNum = new int[2] { num, counter++ };

            bool twoTreesSameSize = setLow.Count == setHigh.Count;          

            if (twoTreesSameSize)
            {
                if (setLow.Count == 0 || newNum[0] <= setLow.Max[0])
                {
                    setLow.Add(newNum);
                }
                else
                {
                    setHigh.Add(newNum);

                    // move the minimum number from setHigh to setLow. 
                    setLow.Add(setHigh.Min);
                    setHigh.Remove(setHigh.Min);
                }
            }
            else if (newNum[0] <= setLow.Max[0])
            {
                setLow.Add(newNum);

                // move the maximum number from setLow to setHigh
                setHigh.Add(setLow.Max);
                setLow.Remove(setLow.Max);
            }
            else
            {
                setHigh.Add(newNum);
            }
    }
    
    public double FindMedian() {
        if (setLow.Count == 0)
            {
                return 0;
            }

            if (setLow.Count == setHigh.Count)
            {
                return (setLow.Max[0] + setHigh.Min[0]) / 2d;
            }
            else
            {
                return setLow.Max[0];
            }
    }
}

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