Find the Kth Largest Element in an Array

First Solution

Sort from largest to smallest, then return the element at index k-1.

Time complexity: n(log n)

int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end(), greater<int>());
    return nums[k-1];
}

Quickselect

Time complexity: average O(n)

This uses the same Partition function as quicksort, but the divide-and-conquer logic differs. Since we want a specific position, we only need to process one side.

int findKthLargest(vector<int>& nums, int k) {
    // Find Kth largest becomes finding the element at position len-k when sorted ascending
    k = nums.size() - k;
    int lo = 0;
    int hi = nums.size() - 1;
    while(lo < hi) {
        int i = partition(nums, lo, hi);
        // Found when exactly K elements are smaller than pivot
        if (i == k) {
            break;
        } else if (i > k) {
            // More than K elements smaller than pivot, target must be in first half
            hi = i - 1;
        } else {
            // Fewer than K elements smaller than pivot, target must be in second half
            lo = i + 1;
        }
    }
    return nums[k];
}

// Same partition algorithm as quicksort
int partition(vector<int>& nums, int st, int end) {
    int pivot = nums[end];
    int i = st - 1;
    for(int j = st; j < end; ++j) {
        if (nums[j] < pivot) {
            ++i;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[end], nums[i+1]);
    return i+1;
}

Heap Solution - For Massive Data

Time complexity: n log(k)

Works well when n is large but k is small.

Use max heap, build once then take K times
Use min heap of K elements. When capacity exceeds K, check if top element is smaller than new element. If so, pop top and insert new element. Maintain until end of data.
Use ordered containers like set or multiset - similar idea.

#heap

Find Peak Element Find the Town Judge