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.

Example 1:

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

Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution: Using Quick Sort

This problem can be naive using build-in sorting or priority_queue.

The idea is to use the partition feature of quick sort to find the kth largest number.

int partition(vector<int> &arr, int low, int high) {
    int pivot = arr[high];
    int index = low - 1; // end index of left part
    for (int i=low; i<=high; i++) {
        if (arr[i] <= pivot) {
            index += 1;
            swap(arr[index], arr[i]);
        }
    }
    return index;
}

int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pos = partition(nums, left, right);
        if (pos == nums.size() - k) return nums[pos];
        else if (pos > nums.size() - k) right = pos - 1;
        else left = pos + 1;
    }
}