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 :)
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.
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.
This follows Gayle Laakmann McDowell's approach published by HackerRank (see here) but in Python 3:
import heapq def addNum(num, lowers, highers): if not lowers or num < -lowers[0]: heapq.heappush(lowers,-num) else: heapq.heappush(highers,num) def rebalance(lowers, highers): if len(lowers) - len(highers) >= 2: heapq.heappush(highers,-heapq.heappop(lowers)) elif len(highers) - len(lowers) >= 2: heapq.heappush(lowers,-heapq.heappop(highers)) def getMedian(lowers, highers): if len(lowers) == len(highers): return (-lowers[0] + highers[0])/2 if len(lowers) > len(highers): return float(-lowers[0]) else: return float(highers[0]) def runningMedian(a): lowers = [] # max heap, vals should go in and come out negated highers = [] # min heap, vals should go in positive result = [] for v in a: addNum(v, lowers, highers) rebalance(lowers, highers) result.append(round(getMedian(lowers, highers),1)) return result
Unfortunately, the heapq module is not object-oriented, only implements a min-heap discipline, and does not provide the ability to use a custom comparator, which would make this way easier with regard to the max-heap.
/* thanks Gayle for explaining the heap based approach ( https://www.youtube.com/watch?v=VmogG01IjYc ) the idea is to keep 2 heaps minHeap and maxHeap, during the traversal on input maintain heaps such that if we maintain the median position at the top. */
int main() { int n,x; cin>>n; auto cmpSmaller = [](int a, int b){return a>b;}; auto cmpBigger = [](int a, int b){return a<b;}; priority_queue<int,vector<int>,decltype(cmpSmaller)> maxHeap(cmpSmaller); priority_queue<int,vector<int>,decltype(cmpBigger) > minHeap(cmpBigger); auto pushInHeap = [&minHeap , &maxHeap](int data) { if(minHeap.empty() or minHeap.top()>data) minHeap.push(data); else maxHeap.push(data); }; auto balanceHeap = [&minHeap , &maxHeap]() { int miSize = minHeap.size() , mxSize = maxHeap.size(); if(abs(miSize - mxSize) >= 2) { if(miSize > mxSize) maxHeap.push( minHeap.top() ) , minHeap.pop(); else minHeap.push( maxHeap.top() ) , maxHeap.pop(); } }; auto getMedian = [&minHeap , &maxHeap]() { int miSize = minHeap.size() , mxSize = maxHeap.size(); if(miSize == mxSize) { double x = minHeap.top(); double y = maxHeap.top(); return (x+y)/2; } else return double( (miSize < mxSize) ? maxHeap.top() : minHeap.top()); }; while(n--) { cin>>x; pushInHeap(x); balanceHeap(); cout<<setprecision(1)<<fixed<<getMedian()<<'\n'; } }
Sort 209 Discussions, By:
Please Login in order to post a comment