Find the N'th highest number in unsorted array

Question

Today in a interview, I was told to write a program which will output the nth highest number in the unsorted array,

I solved this using javascript, the program is as follows,

var fn50 = function(){
    var reverseSort = function(myArray,highest){
        var x = 0,
            y = 0,
            z = 0,
            temp = 0,
            totalNum = myArray.length, // total numbers in array
            flag = false, // is the numbers sorted in reverse while iteration
            isAchieved = false; // whether we achieved the nth highest

        while(x < totalNum){
            y = x + 1; // start comparing 'yth' number which is next to 'xth' number.

            if(y < totalNum){
                // start comparing 'xth' with the next number, and if 'xth' number less than its next position number, just swipe them
                for(z = y; z < totalNum; z++){

                    if(myArray[x] < myArray[z]){
                        temp = myArray[z];
                        myArray[z] = myArray[x];
                        myArray[x] = temp;
                        flag = true; // if number swiping done ?
                    }else{
                        continue;
                    }   
                }                   
            }

            if(flag){
                flag = false;
            }else{
                x++; // x holds the max number in series, now move to next position to find next highest number 
                if(x > highest){ // if x is what the desired max number which we want flag it and break the loop to escape further iteration.
                    isAchieved = true;
                }   
            }
            if(isAchieved){
                break;
            }
        }

        print(myArray[(highest - 1)]);  
    };

    reverseSort([12,56,78,34,11,100,95],4); // passing the unsorted array of number's, and finding the 4th highest number
};

fn50();

I got the desired output i.e the answer is 56 from the above array which is the 4th highest number.

But the interviewer told for a better solution.

Can you tell me or give me a hint, how can there be a better solution. Some data structure technique ?

Answer 1

Sorting and selecting the kth highest number needs O(n log(n)) time, where n is the number of elements. In the bibliography, there is the medians of medians algorithm, that allows us to select the kth highest or smallest in linear time, no matter what value k has. You could find out if the interviewer had this kind of algorithm in mind, if you asked if the desired element could be the median of the array. The median is the element at position n / 2, which is considered the hardest case.

But for an interview, it's a complicated algorithm. If k is in general small, you can apply the following algorithm, based on the structure of a heap. You convert the array into a heap in linear time. Then you extract k times the largest element. This will take O(n + k * log(n)) time, which for small k = ο(n / log(n) is linear.

Having k be as small as a constant number, like 4, has an even simpler linear algorithm. Every time we scan the array and remove the largest. This will take O(k * n) time and because k is constant, O(k * n) = O(n).

Answer 2

I tried to implement this with quickselect as JuniorCompressor suggested. But I wonder if that is really the fastest possible way. I guess the calculation of the pivot could be made more efficient.

var nthLargest = function(list, n) {
  var i, a = 0, b = list.length, m, pivot;
  if(n < 1) throw new Error("n too small");
  if(list.length < n) throw new Error("n too large");
  list = list.slice(0);
  var swap = function(list, a, b) {
    var temp = list[a];
    list[a] = list[b];
    list[b] = temp;
  }
  //returns the index of the first element in the right sublist
  var partition = function(list, pivot, a, b) {
    b--;
    while(a <= b) {
      if(list[a] <= pivot) a++;
      else if(list[b] > pivot) b--;
      else swap(list, a, b);
    }
    return a;
  }
  while(b - a > 1) {
    for(i = a, pivot = 0; i < b; i++) {
      pivot += list[i];
    }
    pivot /= b-a;
    m = partition(list, pivot, a, b);
    if(b - m >= n) a = m; // select right sublist
    else { // select left sublist
      if(m === b) return list[a]; // all elements in sublist are identical
      n -= b - m;
      b = m;
    }
  }
  if(n !== 1) throw new Error();
  return list[a];
}