The question

Given an array of integers find the kth element in the sorted order (not the kth distinct element). So, if the array is [3, 1, 2, 1, 4] and k is 3 then the result is 2, because it’s the 3rd element in sorted order (but the 3rd distinct element is 3).

My solution

This doesn’t sound as a very hard problem but I couldn’t find a solution better than:

– Sort using quicksort

– Return the element at index k

The complexity of this solution is the complexity of quicksort O(nlogn).

The best solution

The best solution is a family of algorithms called “selection algorithm” which serves exactly this purpose. Most specifically quickselect can be used:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
var arr = [1, 5, 6, 6, 9, 2, 3, 3, 4, 3, 1, 9, 4, 5, 7, 7, 1];

function partition(arr, left, right, pivot) {
  // Move pivot to the end
  var tmp;
  tmp = arr[pivot];
  arr[pivot] = arr[right];
  arr[right] = tmp;

  // This is the index that divides lower and higher numbers
  var swapIndex = left;

  for (var i = left; i < right; i++) {
    // Check if current value is lower than pivot value
    if (arr[i] < arr[right]) {
      tmp = arr[i];
      arr[i] = arr[swapIndex];
      arr[swapIndex] = tmp;
      swapIndex++;
    }
  }

  // Move pivot value to where it should be
  tmp = arr[right];
  arr[right] = arr[swapIndex];
  arr[swapIndex] = tmp;

  return swapIndex;
}

function select(arr, left, right, k) {
  // I don't care very much about the pivot now. I'm just choosing the middle.
  var pivot = parseInt((left + right) / 2, 10);
  var res = partition(arr, left, right, pivot);

  if (res === k) {
    return arr[res];
  }

  if (k < res) {
    return select(arr, left, res - 1, k);
  } else {
    return select(arr, res + 1, right, k);
  }
}

function test() {
  var found = select(arr, 0, arr.length -1, 6);

  if (found === 3) {
    console.log('success');
  }
}

test(); // Prints success
[ application_design  computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
Load testing a Rails app with Vegeta application_design programming
House painting problem computer_science algorithms javascript programming