5
3
8
1
9
[0][1][2][3][4]
sorted so far
Brute force · keep a sorted list
▸1sorted = []2on addNum(x):3 insert x keeping sorted order // O(n)4on findMedian():5 return middle (or avg of two middles)
state
- stream[5, 3, 8, 1, 9]
Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.
Try one problemDesign a data structure that supports adding integers from a stream and returning the median of all values seen so far at any time. The median is the middle value, or the average of the two middle values when the count is even.
▸1sorted = []2on addNum(x):3 insert x keeping sorted order // O(n)4on findMedian():5 return middle (or avg of two middles)
line 1Numbers arrive one at a time; after each, report the MEDIAN of everything so far. Simple plan: keep the values in a SORTED list, then the median is just the middle (or the average of the two middles).