What is the approach to this problem? I've tried a bunch of methods like stuff


#1

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.


#2

you should go for quick select using median …http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/


#3

Parveen Rohilla We can’t apply as it include swaps of elements which is prohibited by problem statement…


#4

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


#5

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.?


#6

@guest_user_251 is wrong for so many reasons… some are that this array is read only and that the numbers aren’t distinct… you should use O(1) extra space.

@eli-weiss, that’s nice but isn’t it O(n * n) time complexity? think of a sorted array… will take n * n