Maintain a Streaming Median

You are designing a component that receives integers one at a time and must return the current median after each update.

Example:

• After processing [2, 3, 1], the median is 2.
• After processing one more value to form [2, 3, 1, 4], the median is (2 + 3) / 2 = 2.5.

Implement a data structure with two operations:

• add(x): insert an integer
• getMedian(): return the median of all inserted values so far

Discuss the time complexity of your approach.

Follow-up: if the full input array is available up front and you want to avoid extra auxiliary space, how would you compute the median while minimizing additional memory usage?