Only 3 test cases are being passed. Please help with this.
TLE Error - Mike and HashTrick
@koshimagoyal97
The code you provided was giving TLE in 3 cases,and your logic was absolutely correct.
The Reason for TLE was your Quicksort which in worst case was taking O(n^2) time.
The Solution need to be given in O(n) ya O(nlogn),as the Constraints over n is 10^5;
The way i thought is why to add in an Array and then sort it using QuickSort or MergerSort or Inbuilt Arrays.sort.
I directly sorted my map on the basis of Values,which reduced my sorting time to O(nlog n) from O(n^2),as sorting HashMap by value took O(nlogn) time.
And as you are calling map or passing in parameters of a function quite a lot,so I made it static.
Other ways to explore:
- We can sort HashMap by some other methods too.
- We can use Arrays.sort with Comparator to sort on the basis of comparison from HashMap.
I hope this will surely help you.
Please Hit like if i resolved your doubt satisfactorily else revert back here
1 Like