Leetcode: Kth Largest Element in an Array

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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

A max-heap solution:
First of all, put all elements into the heap. Then poll the top k elements from the max heap then we get the result. The time complexity for max heap is  O(n) + O(k * logn). The space complexity is O(n).

Code (Java):

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(nums.length, Collections.reverseOrder());
        
        for (int num : nums) {
            maxHeap.offer(num);
        }
        
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.poll();
        }
        
        return result;
    }
}

A min-heap solution:
 -- Step 1: put the first k elements into the heap. Time complexity is O(k). 
 -- Step 2: Start from elements k + 1 to n, compare each one with heap.peek(). If greater than the peek, replace with the element. The time complexity is O((n - k) logk).
  -- Step 3: After we iterate the array, the heap stores the top k elements, and the kth largest element is the minimum element of the heap, which is peek.

The space complexity is O(k). 

Code (Java):

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            } else {
                if (num > maxHeap.peek()) {
                    maxHeap.poll();
                    maxHeap.offer(num);
                }
            }
        }
        
        return maxHeap.peek();
    }
}

A quick-selection algorithm:
The quick selection algorithm is very similar to quick sort. Instead of sorting, it only needs the partition step, where it finds the pivot and compare the pivot with k. 

There is post for the quick sort. 
http://buttercola.blogspot.com/2014/12/data-structure-algorithms-sorting.html

Code (Java):

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        return findKthLargestHelper(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int findKthLargestHelper(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return nums[lo];
        }
        
        int pivot = partition(nums, lo, hi);
        if (pivot == k) {
            return nums[k];
        }
        
        if (pivot > k) {
            return findKthLargestHelper(nums, lo, pivot - 1, k);
        } else {
            return findKthLargestHelper(nums, pivot + 1, hi, k);
        }
    }
    
    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i = lo + 1;
        int j = hi;
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
            }
        }
        
        swap(nums, lo, j);
        
        return j;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Since it only uses the partition algorithm, the average time complexity is O(n). However, the worst case complexity is O(n^2). 

In which case the quick selection has time complexity of O(n^2)?
Let's say you have a sorted array, 1 2 3 4 5, and k = 1, means we select the largest element which is 5. For each element in the array, we need to run the partition algorithm and discard the pivot only, which has the time complexity of O(n). For the n elements in the array, the overall time complexity is O(n^2). Therefore, for either quick sort and quick select algorithm, we usually need to well suffle the array for the reason each time the pivot is chosen in the half.