215. Kth Largest Element in an Array

📝 Problem Details

• Title: 215. Kth Largest Element in an Array
• Link: https://leetcode.com/problems/kth-largest-element-in-an-array/
• Difficulty: Medium
• Tags/Categories: Priority-Queue

input array nums input integer k return the kth largest element in the array follow up: can you do this without sorting?

💭What Were My Initial Thoughts?

trivial approach would be to sort the array in descending order and return the k-1th element

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

a more optimized approach could be to use a priority queue or min heap
we keep a min-heap of fixed size k
when the heap exceeds this size we pop

💡 Explanation of Solution

1. Initialize a min-heap heap.
2. Iterate over the input. For each num:
   • Push num onto the heap.
   • If the size of heap exceeds k, pop from heap.
3. Return the top of the heap.

⌛ Complexity Analysis

Time Complexity: O(n log k)
- the limited size of the heap being of size k makes it more efficient than a traditional sort

Space Complexity: O(k)

💻 Implementation of Solution

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
 
        for(int num : nums) {
            pq.push(-num);
            if(pq.size() > k) {
                pq.pop();
            }
        }
        return -pq.top();
    }
};