Kth Largest in unsorted Array

Naive Approach#

Sort the array in descending order and return the element at index k-1. Simple but O(n log n) and sorts the entire array when only the k-th element is needed.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.rbegin(), nums.rend());
        return nums[k-1];
    }
};

Time Complexity: O(nlogn)

Space Complexity: O(1)

Better Approach - Use Min Heap#

Maintain a min-heap of size at most k. Insert each element; if the heap exceeds size k, pop the minimum. After processing all elements the heap contains the k largest elements seen, and its minimum (the top) is the k-th largest. Each push/pop is O(log k), giving O(n log k) overall — significantly faster than full sorting when k is small.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>, greater<int>> pq;

        for(int i=0;i<k;i++)
        {
            pq.push(nums[i]);
        }

        for(int i=k;i<nums.size();i++)
        {
            pq.push(nums[i]);
            if(pq.size()> k)
                pq.pop();
        }
        return pq.top();
    }
};

Time Complexity: O(nlogk)

Space Complexity: O(1)