What is the approach to this problem? I’ve tried a bunch of methods like stuff … (I dont wanna reveal the probable methods). Anyway, I tried doing it in C++. It threw a TLE ( Memory limit). I used the exact same approach in Python and its accepted. Could you direct me with a proper approach. Thanks.
you should go for quick select using median …http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/
Parveen Rohilla We can’t apply as it include swaps of elements which is prohibited by problem statement…
I used the following approach:
iterate over the list with the first element and count how many numbers are lower
- if it is less than B - then keep it as lower reference --> every number lower than this will be eliminated without iteration over A
- if it is more than B - then keep it as higher reference --> every number bigger than this will be eliminated
- if it is exactly B - then return
while doing this you are closing in for the number and eliminate statistically most of the input
in case you finished the iteration then you return more as it appeared more than once
what are you doing after getting this lower and higher reference.if you iterating again then it will become worst case O(N^2) Algorithm. Won’t it.?