175. Find the Running Median of a Stream of Integers

Given n integers arriving one at a time, after each new integer arrives print the median of all integers seen so far, rounded to exactly one decimal place. Print all n medians space-separated on one line.

Input: The first line contains an integer n. The second line contains n space-separated integers, the stream of arriving values in order. Output: Print n numbers, space-separated on one line - the running median after each new integer, each rounded to exactly one decimal place.

1 <= n <= 10^5

Using a MAX-heap for the LOWER half and a MIN-heap for the UPPER half (not the reverse) is what gives instant O(1) access to exactly the two 'middle' values needed for the median - a natural but easy-to-mix-up detail.

As numbers arrive one at a time, print the median of everything seen so far, after every single new number. Brute force: Keep a running sorted list, inserting each new number into its correct sorted position (or re-sorting from scratch each time) - insertion into a sorted array/list costs O(n) per number, giving O(n²) total for n numbers. Optimised: The 'two balanced heaps' technique keeps BOTH insertion and median-retrieval fast: inserting a new number costs O(log n) (heap push, plus a possible O(log n) rebalancing move), and retrieving the current median is always O(1) - a huge improvement over repeated O(n) sorted insertions.

Keep the array always sorted: for each new number, binary search for its correct insertion position in O(log n), then shift the later elements over by one slot to make room and insert it there, after which the median is always readable in O(1) from the middle of the array. This avoids the brute approach's wasteful full re-sort on every step, since the array never becomes unsorted in the first place, though the shifting still costs linear time per insertion in the worst case. Time: O(n^2) Space: O(n)

Maintain a max-heap holding the smaller half of the numbers seen so far and a min-heap holding the larger half, keeping their sizes balanced to differ by at most one element; insert each new number into the appropriate heap based on comparison with the heaps' tops, then rebalance by moving the top of one heap to the other if the size difference exceeds one. The median is then always either the top of the larger heap or the average of both tops, readable in O(1), with each insertion costing only a logarithmic heap operation instead of a linear array shift - the standard technique for a running median. Time: O(n log n) Space: O(n)

Keep every number seen so far in a plain array; whenever a new number arrives, append it, then make a sorted copy of the entire array from scratch and read off the middle element (or average the two middle elements for an even count) as the median. This is correct because sorting always gives the true order, but repeating a full O(n log n) sort after every single insertion makes the overall stream processing extremely slow. Time: O(n^2 log n) Space: O(n)

1. Maintain TWO heaps: a max-heap holding the smaller HALF of the numbers seen so far, and a min-heap holding the larger half. 2. Keep their sizes balanced (differing by at most 1) after every single insertion, moving an element between the two heaps if needed. 3. The median is either the top of whichever heap is larger (if sizes differ), or the average of both tops (if sizes are equal).

Time: O(n log n) total for n numbers - each insertion costs O(log n). Space: O(n), for the two heaps holding all numbers seen so far.

n = 1 (median equals that single value), and n = 10^5 to confirm the two-heap balancing scales; medians alternate between a single middle value (odd count so far) and the average of two middles (even count so far).

This is one of the most iconic 'two heaps' interview problems - be ready to explain the rebalancing step clearly (moving the max-heap's top to the min-heap, or vice versa, whenever sizes drift apart by more than 1).