We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Why not use a heap (PriorityQueue in Java) to remove the need for the O(nlog(n)) operation of sorting the array. Adding to a heap is O(log(n)) in worst-case, but O(1) in the average case. Since that happens n times, it should be faster on average. See my implementation:
// Complete the luckBalance function below.staticintluckBalance(intk,int[][]contests){intnumLuck=0;inttotalImportant=0;PriorityQueue<Integer>minHeap=newPriorityQueue<Integer>(newComparator<Integer>(){@Overridepublicintcompare(Integerobj1,Integerobj2){returnobj1-obj2;}});for(int[]contest:contests){numLuck+=contest[0];if(contest[1]==1){minHeap.offer(contest[0]);totalImportant++;}}for(inti=0;i<totalImportant-k;i++){numLuck-=2*minHeap.poll();}returnnumLuck;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Luck Balance
You are viewing a single comment's thread. Return to all comments →
Why not use a heap (PriorityQueue in Java) to remove the need for the O(nlog(n)) operation of sorting the array. Adding to a heap is O(log(n)) in worst-case, but O(1) in the average case. Since that happens n times, it should be faster on average. See my implementation: