Why it works
- A number goes to low only if it is no bigger than the top of low, and a number moves only as a top. So everything in low stays at or below everything in high.
- After each addNum, low has the same size as high or one more. So the middle of the sorted numbers is right at the tops: the top of low, or the average of both tops.
- The 5 shows why both moves are needed: the 1 puts low two ahead and 5 goes to high; the 9 puts high ahead and 5 comes back.
Complexity
addNum: time O(log n), at most two pushes and one pop. findMedian: time O(1), it only reads the tops. Memory O(n) for all the numbers.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗