Live Median House Price
A local news site has a housing page with one headline number: the median sale price in town this year. The median, not the average, because one mansion selling for millions would drag the average far above what a typical home costs.
Sales are reported one at a time as they close, and the page shows the updated median right away. By the end of the year there are thousands of sales, and recomputing from scratch every time makes the page slow.
Your task
Write a class MedianPrice:
constructor(): no sales yet.addSale(price): record one sale.median(): return the median of all prices recorded so far. With an odd number of sales it is the middle price once they are sorted; with an even number it is the average of the two middle prices (which may end in .5). With no sales, returnnull(Nonein Python).
addSale should take O(log n) time and median O(1), where n is the number of sales so far.
class MedianPrice
Examples
new MedianPrice() .addSale(300000) .median() .addSale(250000) .median() .addSale(2000000) .median() .addSale(280000) .median()
[null, null, 300000, null, 275000, null, 300000, null, 290000]
One sale: 300000. Two sales, 250000 and 300000: the average of the two is 275000. Add the 2,000,000 mansion: the sorted prices are 250000, 300000, 2000000, so the median is 300000; the mansion barely moves it. Add 280000: the middle two are 280000 and 300000, median 290000.
new MedianPrice() .median() .addSale(5) .addSale(6) .median()
[null, null, null, null, 5.5]
Before any sale there is no median: null. After 5 and 6 the median is 5.5, so the answer is not always a whole number.
Constraints
- 1 ≤ price ≤ 10,000,000 (whole dollars). Prices may repeat.
- At most 50,000 calls in total.
- Every median is a whole number or ends in .5, so answers are compared exactly.
Start with brute force
Keep all prices in a list and sort it every time median() is called. That costs O(n log n) per call, so a year of 25,000 sales with a median after each is about 4 billion steps.
Keeping the list sorted by inserting each price in its place (binary search for the spot) is better, but inserting into the middle of an array still shifts up to n elements, so it is O(n) per sale and O(n²) for the year.
Hints
0 of 4 shown- Hint 1
Suppose the sorted prices are split into a lower half and an upper half. To read the median, which prices do you actually need to see? Do you need the rest of each half in order?
- Hint 2
You only need the largest price of the lower half and the smallest price of the upper half. Everything else in each half can stay unordered.
- Hint 3
A max-heap keeps the largest of the lower half on top; a min-heap keeps the smallest of the upper half on top. When a new sale arrives, how do you put it in the right half, and how do you stop the halves from drifting apart in size?
- Hint 4
Keep
low(a max-heap) andhigh(a min-heap) withlowholding the same number of prices ashighor one more. To add: push ontolow, movelow's top tohigh, and ifhighis now bigger, movehigh's top back. The median islow's top for an odd count, or the average of both tops for an even count.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The median only depends on the one or two prices in the middle. Split the sales into a lower half and an upper half. Keep the lower half in a max-heap so its largest price is on top, and the upper half in a min-heap so its smallest price is on top. Those two tops sit right at the middle.
Two rules keep it correct: every price in low is ≤ every price in high, and low has the same size as high or one more. Pushing into low and then passing low's top to high keeps the first rule; moving one back when high gets too big keeps the second.
Trace the first example (prices in thousands):
- add 300: low {300} → pass 300 to high → high is bigger, move it back. low {300}, high {}. Median 300.
- add 250: low {300, 250} → pass the top, 300, to high. low {250}, high {300}. Sizes equal. Median (250 + 300) / 2 = 275.
- add 2000: low {2000, 250} → pass 2000 to high. high {300, 2000} is bigger, so move 300 back. low {300, 250}, high {2000}. Median 300.
- add 280: low {300, 280, 250} → pass 300 to high. low {280, 250}, high {300, 2000}. Median (280 + 300) / 2 = 290.
Step 3 shows why the price goes through low first: the mansion landed in the upper half, where it belongs, and could not pull the median up.
class MedianPrice {
constructor() {
this.low = new Heap((a, b) => a > b); // max-heap: lower half
this.high = new Heap((a, b) => a < b); // min-heap: upper half
}
addSale(price) {
this.low.push(price);
this.high.push(this.low.pop()); // the largest of low may belong in high
if (this.high.size() > this.low.size()) this.low.push(this.high.pop());
}
median() {
if (this.low.size() === 0) return null;
if (this.low.size() > this.high.size()) return this.low.top();
return (this.low.top() + this.high.top()) / 2;
}
}
class Heap { // before(a, b): a should sit above b
constructor(before) { this.a = []; this.before = before; }
size() { return this.a.length; }
top() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
for (let i = a.length - 1; i > 0; ) {
const p = (i - 1) >> 1;
if (!this.before(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ; ) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.before(a[l], a[m])) m = l;
if (r < a.length && this.before(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}import heapq
class MedianPrice:
def __init__(self):
self.low = [] # lower half as a max-heap (values negated)
self.high = [] # upper half as a min-heap
def add_sale(self, price):
heapq.heappush(self.low, -price)
# the largest of low may belong in high
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def median(self):
if not self.low:
return None
if len(self.low) > len(self.high):
return float(-self.low[0])
return (-self.low[0] + self.high[0]) / 2Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.