Middle Score After Each Entry
Problem
Scores arrive one at a time. After each arrival, report the middle score of everything seen so far. When the number of scores is even, report the lower of the two middle scores. Return the list of reports, and aim for better than sorting all the scores again after every arrival.
Examples
Input: scores = [5, 15, 1, 3]
Output: [5, 5, 5, 3]
Why: after all four arrive the sorted scores are 1, 3, 5, 15, and the lower middle is 3Input: scores = [2, 2, 2]
Output: [2, 2, 2]Input: scores = []
Output: []
Why: edge case, no arrivals means no reportsHints
0 / 3
Re-sorting after each arrival costs n log n per report. The middle only depends on where the lower half ends and the upper half begins.
Split the scores into a lower half and an upper half. The report is the largest score of the lower half, as long as the lower half holds the extra score when the count is odd.
Keep the lower half in a max-heap and the upper half in a min-heap. Push each score into the side it belongs to, move one score across if the lower half gets more than one bigger or the upper half gets bigger, and report the top of the lower half.
Solution
The two-heaps pattern keeps the sorted order split at the middle without ever sorting: a max-heap holds the lower half, so its top is the largest of the small scores, and a min-heap holds the upper half. The lower half is allowed to be one score bigger, which makes its top the middle for an odd count and the lower middle for an even count, exactly the score to report. A new score goes to the lower half unless it is larger than the lower half's top, and one move across restores the size rule. Python's heapq is a min-heap, so the lower half stores negated scores. Each arrival costs O(log n), so time is O(n log n) overall and space is O(n).
import heapq
def middle_scores(scores):
low, high = [], [] # low: max-heap of negated scores, high: min-heap
reports = []
for s in scores:
if low and s > -low[0]:
heapq.heappush(high, s)
else:
heapq.heappush(low, -s)
if len(low) > len(high) + 1: # lower half too big
heapq.heappush(high, -heapq.heappop(low))
elif len(high) > len(low): # upper half too big
heapq.heappush(low, -heapq.heappop(high))
reports.append(-low[0]) # top of the lower half
return reports
print(middle_scores([5, 15, 1, 3])) # -> [5, 5, 5, 3]
print(middle_scores([2, 2, 2])) # -> [2, 2, 2]
print(middle_scores([])) # -> []Stuck on the idea rather than the code? Two Heaps: Running Median covers it.