Description

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.

Solution

MinHeap, O(n * logk), S(k)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        
        for (int n : nums) {
            if (queue.size() < k) {
                queue.offer(n);
            } else if (n > queue.peek()) {
                queue.poll();
                queue.offer(n);
            }
        }
        
        return queue.peek();
    }
}

Quick-sort partition, time O(n), space O(1)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKth(nums, 0, nums.length - 1, nums.length - k);
    }
    // find the kth (start from 0) element in sorted nums
    private int findKth(int[] nums, int start, int end, int k) {
        int pivotIndex = partition(nums, start, end);
        
        if (pivotIndex < k) {
            return findKth(nums, pivotIndex + 1, end, k);
        } else if (pivotIndex > k) {
            return findKth(nums, start, pivotIndex - 1, k);
        } else {
            return nums[k];
        }
    }
    
    private int partition(int[] nums, int start, int end) {
        int pivot = nums[end];
        for (int i = start; i < end; ++i) {
            if (nums[i] <= pivot) {
                swap(nums, start++, i);
            }
        }
        
        swap(nums, start, end);
        return start;
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}