Reference: LeetCode EPI 11.8
Difficulty: Medium

Problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.

Example: 

1
2
3
4
5
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Analysis

Methods:

  1. Sorting

    • Sort the array and find the index num.length - k element.
      1
      2
      3
      4
      5
      sort
      public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
      }
      Time: $O(N\log{N})$ 3 ms
      Space: $O(1)$

  2. Heap

    • Since our goal is to find the k-th largest element, we need a min heap to store k elements at any time.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minPQ = new PriorityQueue<>((n1, n2) -> (n1 - n2));
        for (int val : nums) {
          minPQ.add(val);
          if (minPQ.size() > k) {
            minPQ.poll();
          }
        }
        return minPQ.poll();
      }
      Time: $O(N\log{k})$ 38 ms
      Space: $O(k)$

  3. Quick Select

    • Using the partition algorithm in quicksort developed by Tony Hoare, also known as Hoare’s selection algorithm.
    • For simplicity, k-th largest element is the same as (N - k)-th smallest element, we then we can implement k-th smallest algorithm for this problem.
    • Notice that this algorithm works well even for arrays with duplicates.
    • Notice that randomly picking a pivot will bring about great performance improvement. Swap the randIdx‘s element with the one at lo.
      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
      public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSelect(nums, n - k, 0, n - 1); // (n-k)-th (from 0)
      }

      // find the k-th element (from 0 ~ hi - 1)
      private int quickSelect(int[] nums, int k, int lo, int hi) {
        if (lo == hi) {  // base case: only one item
          return nums[lo];
        }
        
        // swap randIdx
        Random rand = new Random();
        int randIdx = lo + rand.nextInt(hi - lo + 1);
        swap(nums, lo, randIdx);
        
        int p = lo, i = lo, j = hi + 1; // one offset

        while (true) {
          while (nums[++i] < nums[p]) { // move i
            if (i == hi) break;
          }
          while (nums[--j] > nums[p]) { // move j
            if (j == lo) break;
          }
          if (i >= j) break;
          swap(nums, i, j);
        }

        swap(nums, p, j);

        if (k < j) {
          return quickSelect(nums, k, lo, j - 1);
        } else if (k > j) {
          return quickSelect(nums, k, j + 1, hi);
        } else {
          return nums[j];
        }
      }

      private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
      }
      Time: $O(N)$ in the average case; $O(N^2)$ in the worst case. 1 ms
      Space: $O(1)$