# Find the Running Median

# Find the Running Median

job4year + 5 comments The problem becomes really nice due to time constraints. To solve this problem we will use two heaps minHeap and maxHeap. minHeap would contain all the elements greater than median (of previous iteration) and maxHeap would contain elements smaller than or equal to median(of previous iterations). Now insert the element accordingly and if the difference of size of minHeap and maxHep is greater than 1 , then pop the element from the heap of big size and insert into nextHeap Now 3 cases follow up 1. If minHeap.size()== maxHeap.size() median=(minHeap.top()+ maxHeap.top())/2; 2.Else If minHeap.size()>maxHeap.size() median=minHeap.top(); 3.Else median=maxHeap.top(); //for inserting first two elements, insert bigger element in minHeap and smaller in maxHeap. Hope the solution helps. Ping me if any doubt :)

CiPHeR33 + 1 comment Hey, I find your comment to be very usefull, but there's 1 thing I didn't got, why saving bigger elements in minHeap and smaller elements in maxHeap. Thanks in advance!!

Sid_S + 0 comments The top of minHeap is the smallest element >= the mean

The top of maxHeap is the largest element <= the mean

roughuse07 + 0 comments Thanks for the help, was timed-out before using your little trick :-p

bennattj + 0 comments Agreed, the solution was (somewhat) obvious...my dumbass kept getting errors due to the fact that Java does not automatically convert int's to doubles/float in printf...

NandanHegde2804 + 0 comments "for inserting first two elements, insert bigger element in minHeap and smaller in maxHeap". No need to insert the first 2 elements in this way, just set the median to zero in the beginning and do everything as mentioned inside the loop.

# Here is the implementation in c++

`vector<double> runningMedian(vector<int> a) { vector<double> res; priority_queue<int, vector<int>, greater<int>> minheap; priority_queue<int> maxheap; double median = 0; for (int i=0; i<a.size(); i++) { if (a[i] <= median) { maxheap.push(a[i]); } else { minheap.push(a[i]); } if (minheap.size() > maxheap.size()+1) { maxheap.push(minheap.top()); minheap.pop(); } if (maxheap.size() > minheap.size()+1) { minheap.push(maxheap.top()); maxheap.pop(); } if (minheap.size() == maxheap.size()) { median = (maxheap.top() + minheap.top())/2.0; } else if(minheap.size() > maxheap.size()) { median = (double)minheap.top(); } else if (minheap.size() < maxheap.size()) { median = (double)maxheap.top(); } res.push_back(median); } return res; }`

KA_72 + 0 comments I am coding in cpp, my answer is correct but there is some problem in type casting an int to double, can anyone help me with this?

gschoen + 5 comments Hmmmm, I simply inserted each new number into an array in sorted order (as you would do in an insertion sort) and then used the array indexes to calculate the medians.

My reasoning was that since a print had to be done after each insertion, it would take linear time to print each result.

My maximum running time was 1.72 sec.

Now that I have seen the hints on how the min and max heaps should be used, I guess I should do it properly and see how it affects the running time.

EDIT: I have now re-written the solution using heaps as recommended. The maximum running time is now down to 0.06 sec.

mohit83k + 0 comments WOW

anuj_pancholi_1 + 0 comments Woah, buddy! I did the same thing and timed out in most of the test cases.

zihex + 2 comments I did the same thing, and got similar result. The comparison of maximum running time between sorted array + binary search vs double heaps is like 0.42s vs 0.05s. Implemented in C++.

God_Speed + 0 comments I too implemented using deque and lower_bound . got max execution time of 0.42 secs! But how to use heap in this question?

shakunt_trehan01 + 0 comments [deleted]

alex_khasin + 1 comment How did you measure the running time?

gschoen + 0 comments Apparently you don't anymore :(

When you viewed your submissions, you used to be able to hover your cursor over the result of each test case and it would tell you the running time of that case. That information is no longer made available to you.

shesanmigz + 1 comment [deleted]bennattj + 0 comments [deleted]

RodneyShag + 1 comment ### Java8 solution - passes 100% of test cases

Use 2 heaps to keep track of the median. A heap is basically a PriorityQueue in Java.

import java.util.Scanner; import java.util.PriorityQueue; import java.util.Collections; // - We use 2 Heaps to keep track of median // - We make sure that 1 of the following conditions is always true: // 1) maxHeap.size() == minHeap.size() // 2) maxHeap.size() - 1 = minHeap.size() public class Solution { private static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // keeps track of the SMALL numbers private static PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // keeps track of the LARGE numbers public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int [] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = scan.nextInt(); } scan.close(); medianTracker(array); } public static void medianTracker(int [] array) { for (int i = 0; i < array.length; i++) { addNumber(array[i]); System.out.println(getMedian()); } } private static void addNumber(int n) { if (maxHeap.isEmpty()) { maxHeap.add(n); } else if (maxHeap.size() == minHeap.size()) { if (n < minHeap.peek()) { maxHeap.add(n); } else { minHeap.add(n); maxHeap.add(minHeap.remove()); } } else if (maxHeap.size() > minHeap.size()) { if (n > maxHeap.peek()) { minHeap.add(n); } else { maxHeap.add(n); minHeap.add(maxHeap.remove()); } } // maxHeap will never have fewer elements than minHeap } private static double getMedian() { if (maxHeap.isEmpty()) { return 0; } else if (maxHeap.size() == minHeap.size()) { return (maxHeap.peek() + minHeap.peek()) / 2.0; } else { // maxHeap must have more elements than minHeap return maxHeap.peek(); } } }

From my HackerRank Java solutions.

rishabh0_9 + 1 comment ### Here is my code, and all the test cases have failed except the first one.

`int n = a.length; double[] db = new double[n]; PriorityQueue<Integer> minh = new PriorityQueue<Integer>(); PriorityQueue<Integer> maxh = new PriorityQueue<Integer>(Collections.reverseOrder()); for(int i=0; i<n; i++){ if(maxh.isEmpty()){ maxh.add(a[i]); } else if(maxh.size() == minh.size()){ if(n<minh.peek()) maxh.add(a[i]); else{ minh.add(a[i]); maxh.add(minh.poll()); } } else if(maxh.size() > minh.size()){ if(n > maxh.peek()){ minh.add(a[i]); } else{ maxh.add(a[i]); minh.add(maxh.poll()); } } if(maxh.size() == minh.size()) db[i] = (maxh.peek() + minh.peek())/2.0; else db[i] = (maxh.peek()); } return db;`

rishabh0_9 + 0 comments Please tell me, what's wrong in it.

tsite + 0 comments This challenge is an inferior version of https://www.hackerrank.com/challenges/median The solution to that challenge also works for this one

BenK10 + 1 comment In the description, the phrase "The next N lines will contain an integer ai each in order" is unclear. I thought it meant all the input is already sorted, which makes the problem trivial. It's not sorted!

AllisonP + 0 comments I made some heavy revisions to this challenge today. Hopefully it's clearer now!

gbhattacharyya2 + 1 comment Here is my implementation using 2 heaps in Java. All testcases passed.

private static DecimalFormat df2 = new DecimalFormat(".#"); private static PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); private static PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); static double[] runningMedian(int[] a) { /* * Write your code here. */ if(a == null || a.length == 0) return new double[]{}; List<Double> res = new ArrayList<>(); for(int n : a) { addNum(n); res.add(findMedian()); //System.out.println(res); } double[] val = new double[res.size()]; val = res.stream().mapToDouble(i->i).toArray(); return val; } public static void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if(maxHeap.size() < minHeap.size()) maxHeap.offer(minHeap.poll()); } public static double findMedian() { if(maxHeap.size() == minHeap.size()) return Double.parseDouble(df2.format((maxHeap.peek() + minHeap.peek())/2.0)); else return Double.parseDouble(df2.format(maxHeap.peek() / 1.0)); }

bhattacharyya_s5 + 0 comments [deleted]

hacker112rank + 1 comment # include

# include

using namespace std;

int main() { int n,x,j; cin>>n; int *arr; float m; arr=new int[n];

`cout<<setprecision(1)<<fixed; for(int i=0;i<n;i++) { cin>>arr[i]; x=arr[i]; j=i-1; while(arr[j]>x && j>=0) { arr[j+1]=arr[j]; j--; } arr[j+1]=x; int n1=i+1; if(n1%2==0) { float p=arr[n1/2]; float q=arr[(n1/2)-1]; m=(p+q)/2; } else { m=arr[n1/2]; } cout<<m<<endl; } return 0;`

}

This is giving timeout error in all testcases except first 3. Please suggest what can be done if I want to use insertion sort method only, no heaps.

piyush_gupta1110 + 0 comments you cant solve the problem using Insertion sort in the given time constraints .

Heap didnt striked me at first , i actually used binary search for insertion rather than insertion sort. Got TLE in only 4 test cases .

But still the problem is designed to use Heap . so "if I want to use insertion sort method only, no heaps." this is not a healthy attitude .

jabongg + 2 comments Here is my code passed only 3 testcases using ArrayList. can't improve much.

//package com.hackerrank.java; /** * Created by ejangpa on 1/19/2017. */ import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class FindtheRunningMedian { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<Integer>(); Scanner in = new Scanner(System.in); int n = in.nextInt(); //int[] a = new int[n]; for(int a_i=0; a_i < n; a_i++){ list.add(in.nextInt()); double median = evaluateRunningMedian(list); System.out.println(median); } } static double evaluateRunningMedian(ArrayList<Integer> list) { Collections.sort(list); double median = 0; if (list.size() == 1) { median = list.get(0); } else { int sizeList = list.size(); if (sizeList % 2 == 0) { double midElementsSum = list.get(((sizeList) / 2) - 1) + list.get(((sizeList) / 2)); median = midElementsSum / 2; } else { median = list.get(((sizeList) / 2)); } } return median; } }

mohit_kakkar + 2 comments I used a binary search tree to read in the list of numbers. Then I am traversing itusing inorder traversal. Sounds fine!! But it times out on test cases 4 and above. Can anyone tell me the mistake?

jayfloAsked to answer + 2 comments You are on a heap challenge! =P

Try to determine how you can use heaps to solve the problem. Keeping all elements in a min heap would allow you to keep track of the smallest integer, whereas a max heap would let you keep track of the largest. How can you combine these ideas so you have easy access to the median element(s)?

mohit_kakkar + 1 comment Initially I used a max heap but the result was same.

jayflo + 5 comments Keeping

**all**elements in a max heap only allows quick access to the maximum integer, not the median. Likewise, keeping**all**elements in a min heap allows quick access to only the minimum element. However, if you put*some*elements in a min heap**and***some*in a max heap, you might be able to find the median quickly. What integers should you store in the min heap? Which should you store in the max heap? How many should each heap hold?mohit_kakkar + 0 comments Thanks for the support !!

angeloyz + 0 comments nice answer without spoiler:)

maximshen + 0 comments This is what hackerrank really needs, not giving the solution directly, but the way to make ppl think themselves. Thanks

vidushig2 + 0 comments hey..how we will solve this question?

mav3n + 0 comments You have told the solution itself instead of giving hint. Lol

kehacker + 1 comment I guess I am not understanding the question properly. We are to calculate the median after each streaming number. I am confused that we need to create heaps and store the values according. Unless we read all the data first and put the ones below median in the min-heap and the ones above the median in max heap and then pop them into a list and calcualte the medians as we do. Am I totally off. My original solution works for the first test and fails all the rest.

radekr_ + 0 comments I don't want to give too big hint so I will only write this: you can move elements between heaps as you read next numbers :)

angeloyzAsked to answer + 0 comments so, what is your time complexity of your method? consider the worst case, you have to compare each former number, so O(n) for each input. when n is big, your algorithm will become more and more slower in linear. In fact, you do not need the binary search tree and you do not have to compare each pair of numbers even in the worst case. in fact, you only care about the numbers in the middle of the input array, using 2 heaps, the time complexity is O(logn) for each input. the hardest point may be which heap should be inserted in and what adpation should be made when the new input comes.

Sort 96 Discussions, By:

Please Login in order to post a comment