Problem of the day
Median for ‘arr’ = [1,2,3,4,5] is 3.
Median for ‘arr’ = [1,2,3,4] is (2+3)/2 = 2.5.
Input:
5
1 1
1 2
2
1 5
2
Output:
1.5
2
Explanation:
MedianFinder() initialises the MedianFinder object.
Add 1 to the data structure ‘arr’, so arr = [1].
Add 2 to arr, so arr = [1,2]
Find Median of current arr, that is (1+2)/2 = 1.5.
Add 5 to arr, so arr = [1,2,5]
Find Median of current arr, that is 2.0.
The first line of the input contains an integer, ‘T’, denoting the number of test cases.
The First line of each test case contains an integer, ‘N’ denoting the number of calls to addNum and findMedian.
Return an integer if the call is made to findMedian.
1 <= T <= 10
-100000 <= nums <= 100000
1 <= N <= 50000
There would be at least 1 element in the data structure before calling findMedian.
Time Limit: 1 sec
2
5
1 1
1 2
2
1 5
2
4
1 1
2
1 5
2
1.5
2
1
3
Test 1:
MedianFinder() initialises the MedianFinder object.
Add 1 to the data structure ‘arr’, so arr = [1].
Add 2 to arr, so arr = [1,2]
Find Median of the current arr, that is (1+2)/2 = 1.5.
Add 5 to arr, so arr = [1,2,5]
Find Median of current arr, that is 2.0
Test 2:
MedianFinder() initialises the MedianFinder object.
Add 1 to the data structure ‘arr’, so arr = [1].
Find Median of current arr, that is 1.0.
Add 5 to arr, so arr = [1,5]
Find Median of current arr, that is (1+5)/2 = 3.0.
2
4
1 1
1 5
1 2
2
5
1 1
1 5
2
1 3
2
2.0
3
3