job4year 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 :)
roughuse07 Thanks for the help, was timed-out before using your little trick :-p
bennattj 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 "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 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 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 WOW
anuj_pancholi_1 Woah, buddy! I did the same thing and timed out in most of the test cases.
zihex 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 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 [deleted]
alex_khasin How did you measure the running time?
gschoen 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 [deleted]bennattj [deleted]
RodneyShag 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 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 Please tell me, what's wrong in it.
tsite This challenge is an inferior version of https://www.hackerrank.com/challenges/median The solution to that challenge also works for this one
BenK10 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 I made some heavy revisions to this challenge today. Hopefully it's clearer now!
gbhattacharyya2 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 [deleted]
hacker112rank 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 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 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 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 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 Initially I used a max heap but the result was same.
jayflo 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 Thanks for the support !!
angeloyz nice answer without spoiler:)
maximshen This is what hackerrank really needs, not giving the solution directly, but the way to make ppl think themselves. Thanks
vidushig2 hey..how we will solve this question?
mav3n You have told the solution itself instead of giving hint. Lol
kehacker 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_ 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 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