Running Median (Median of a Data Stream) - Intuit Online Assessment IGDTUW

Problem Preview

"A stream of financial transactions arrives one at a time. After each transaction is received, determine the **median** of all transaction values seen so far. The median is defined as: * If the number of values is **odd**, the median is the **middle** value after sorting. * If the number of values is **even**, the median is the **average of the two middle values**. Return the median after every insertion. To avoid floating-point precision issues, if the median is not an integer, return it as a value ending in **.5** (or according to the platform's required format). --- ## Input Format * The first line contains an integer **N**, the number of transactions. * The second line contains **N** space-separated integers representing the transaction values. --- ## Output Format Print **N** lines, where the **i-th** line contains the median after processing the first **i** transactions. --- ## Constraints * `1 ≤ N ≤ 2 × 10^5` * `-10^9 ≤ transaction[i] ≤ 10^9` --- ## Sample Input ```text 5 5 15 1 3 8 ``` ## Sample Output ```text 5 10 5 4 5 ``` --- ## Explanation The medians after each insertion are: | Transactions Seen | Sorted Order | Median | | ----------------- | -------------- | ------ | | 5 | 5 | 5 | | 5, 15 | 5, 15 | 10 | | 5, 15, 1 | 1, 5, 15 | 5 | | 5, 15, 1, 3 | 1, 3, 5, 15 | 4 | | 5, 15, 1, 3, 8 | 1, 3, 5, 8, 15 | 5 |"