Problem title
Difficulty
Avg time to solve

Shortest Substring with all characters
Easy
--
Left View Of a Binary Tree
Easy
10 mins
Roman Numeral To Integer
Easy
15 mins
Maximum length pair chain
Moderate
15 mins
Optimal BST
Hard
55 mins
Regular Expression Matching
Hard
25 mins
Rabin Carp
Moderate
10 mins
Insert An Element At Its Bottom In A Given Stack
Easy
15 mins
Preorder Traversal
Easy
15 mins
Print All Subsets
Easy
20 mins
16

Running Median

Difficulty: HARD
Contributed By
Avg. time to solve
46 min
Success Rate
50%

Problem Statement

You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

Input Format :
The first line of input contains an integer 'N', denoting the number of integers in the stream.

The second line of input contains 'N' integers separated by a single space.
Output Format :
Print the running median for every integer added to the running list in one line (space-separated).
Input Constraints
0 <= N <= 10 ^ 5
1 <= ARR[i] <= 10 ^ 5

Time Limit: 1 sec
Sample Input 1 :
6
6 2 1 3 7 5
Sample Output 1 :
6 4 2 2 3 4
Explanation of Sample Output 1 :
S = {6}, median = 6
S = {6, 2} -> {2, 6}, median = 4
S = {6, 2, 1} -> {1, 2, 6}, median = 2
S = {6, 2, 1, 3} -> {1, 2, 3, 6}, median = 2
S = {6, 2, 1, 3, 7} -> {1, 2, 3, 6, 7}, median = 3
S = {6, 2, 1, 3, 7, 5} -> {1, 2, 3, 5, 6, 7}, median = 4
Sample Input 2 :
5
5 4 3 2 1
Sample Output 2 :
5 4 4 3 3
Reset Code
Full screen
copy-code
Console