CODEWITHSUNDEEP
algorithm
Pablo
Pablo

Reputation: 65

Interview Ques - find the KTHSMALLEST element in an unsorted array

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 TLE.
Then i tried to use priority queue [extra memory] which gave me MLE :(

Any idea how to solve the problem with constant extra space and within time limit.

Upvotes: 1

Views: 754

Answers (4)

Ilya Murashov
Ilya Murashov

Reputation: 55

I believe I found a solution that is similar to that of @AliAkber but is slightly easier to understand (I keep track of fewer variables).

It passed all tests on InterviewBit

Here's the code (Java):

public int kthsmallest(final List<Integer> a, int k) {
    int lo = Integer.MIN_VALUE;
    int hi = Integer.MAX_VALUE;
    int champ = -1;

    for (int i = 0; i < a.size(); i++) {
        int iVal = a.get(i);
        int count = 0;

        if (!(iVal > lo && iVal < hi)) continue;

        for (int j = 0; j < a.size(); j++) {
            if (a.get(j) <= iVal) count++;

            if (count > k) break;
        }

        if (count > k && iVal < hi) hi = iVal;
        if (count < k && iVal > lo) lo = iVal;

        if (count >= k && (champ == -1 || iVal < champ))
            champ = iVal;  
    }

    return champ;
}

Upvotes: 0

Anshuman Singh
Anshuman Singh

Reputation: 1

Binary search on the answer for the problem.

2 major observations here :

  • Given that all values in the array are of type 'int', their range can be defined as [0, 2^31]. That would be your search space.
  • Given a value x, I can always tell in O(n) if the kth smallest element is smaller than x or greater than x.

A rough pseudocode : 

start = 0, end = 2^31 - 1
while start <= end
  x = (start + end ) / 2
  less = number of elements less than or equal to x
  if less > k
    end = x - 1
  elif less < k
    start = x + 1
  else
    ans = x
    end = x - 1 
return ans

Hope this helps.

Upvotes: 0

Ali Akber
Ali Akber

Reputation: 3800

You can use a O(n^2) method with some pruning, which will make the program like O(nlogn) :)

  1. Declare two variable low = maximum value which position is less than k and high = lowest value which position is greater than k
  2. Keep track of the low and high value you already processed.
  3. 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 TLE and MLE :)

Have a look at my code :

int low=0,high=1e9;
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
      continue;
    int cnt=0,cnt1=0; // cnt is for the strictly less value and cnt1 for same value. Because value can be duplicate.
    for(int j=0;j<n;j++)
    {
        if(i!=j&&A[i]>A[j])
          cnt++;
        if(A[i]==A[j])
          cnt1++;
        if(cnt>k)
          break;
    }
    if(cnt+cnt1<k)
      low=A[i]+1;
    else if(cnt>=k)
      high=A[i]-1;
    if(cnt<k&&(cnt+cnt1)>=k)
    {
        return A[i];
    }
}

Upvotes: 2

amit
amit

Reputation: 178531

You can do an in-place Selection Algorithm.

The idea is similar to quicksort, but recurse only on the relevant part of the array, not all of it. Note that the algorithm can be implemented with O(1) extra space pretty easily - since it's recursive call is a tail call.

This leads to an O(n) solution on average case (just be sure to pick a pivot at random in order to make sure you don't fall into pre-designed edge cases such as a sorted list). That can be improved to worst case O(n) using median of median technique, but with significantly worse constants.

Upvotes: 0

Related Questions