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?