This problem asked to find k'th smallest element in an unsorted array of non-negative integers.
Here main problem is memory limit :( Here we can use constant extra space.
First I tried a
O(n^2) method [without any extra memory] which gave me
Then i tried to use
priority queue [extra memory] which gave me
Any idea how to solve the problem with constant extra space and within time limit.
Best How To :
You can use a
O(n^2) method with some pruning, which will make the program like
- Declare two variable
low = maximum value which position is less than k and
high = lowest value which position is greater than k
- Keep track of the
high value you already processed.
- Whenever a new value comes check if it is in the
[low , high] boundary. If
yes then process it otherwise skip the value.
That's it :) I think it will pass both
Have a look at my code :
for(int i=0;i<n;i++) // n is the total number of element
if(!(A[i]>=low&&A[i]<=high)) // A is the array in which the element are saved
int cnt=0,cnt1=0; // cnt is for the strictly less value and cnt1 for same value. Because value can be duplicate.