Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Example:

Input:

nums = [3,2,1,5,6,4], k = 2

Output:

5

Constraints:

• 1 <= k <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4

Optimal Approach: Min-Heap (Priority Queue)

Explanation:

1. Use a Min-Heap of size k: Store only the k largest elements.
2. Iterate through nums, pushing elements into the heap.
3. If the heap size exceeds k, pop the smallest element.
4. The root of the heap is the kth largest element.

C++ Implementation (LeetCode-Compatible)

#include <vector>
#include <queue>
using namespace std;

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

Step-by-Step Explanation

• Min-Heap of size k ensures that the k largest elements are always retained.
• Push elements into heap and remove the smallest whenever size exceeds k.
• The top element is the answer since it's the kth largest.

Dry Run Example:

Input:

nums = [3,2,1,5,6,4], k = 2

Execution Steps:

Alternative Approaches & Why Not?

QuickSelect (Alternative)

#include <vector>
using namespace std;

class Solution {
public:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] >= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[right]);
        return i;
    }
    
    int quickSelect(vector<int>& nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) return nums[k];
        else if (pivotIndex < k) return quickSelect(nums, pivotIndex + 1, right, k);
        else return quickSelect(nums, left, pivotIndex - 1, k);
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, k - 1);
    }
};

Why is QuickSelect Less Optimal?

• Average Case: O(N), but Worst Case: O(N²).
• Unstable Partitioning can degrade performance.
• In-Place Algorithm but requires careful implementation.

Best Solution & Why?

Why is Min-Heap Best?

• Consistent O(N log k) Performance ✅
• Efficient Memory Usage (O(k)) ✅
• Stable & Easy to Implement ✅

Conclusion

• Best Solution: Min-Heap (Priority Queue).
• Why? Efficient O(N log k) time, stable performance, and simple implementation.
• Alternative Solutions: Sorting (extra computation), QuickSelect (unstable worst case).

Practice More:

• Top K Frequent Elements
• Find Median from Data Stream
• K Closest Points to Origin

Sandip Mhaske

Senior Engineer • Author of 675 guides • Follow for System Design & .NET deep-dives

About