LeetCode Solution 215 - Kth Largest Element in an Array

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:

Step	Heap Content
1	[3]
2	[2, 3]
3	[1, 2, 3] (pop 1) → [2, 3]
4	[2, 3, 5] (pop 2) → [3, 5]
5	[3, 5, 6] (pop 3) → [5, 6]
6	[4, 5, 6] (pop 4) → [5, 6]
Result	5

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Sorting	O(N log N)	O(1)	Sorting is unnecessary
Max-Heap (Priority Queue)	O(N log k)	O(N)	Uses extra space
QuickSelect (Hoare's Algorithm)	O(N) avg, O(N^2) worst	O(1)	Unstable worst-case

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?

Approach	Time Complexity	Space Complexity	Best Choice?
Min-Heap (Priority Queue)	O(N log k)	O(k)	✅ Best balance
Sorting	O(N log N)	O(1)	❌ Slower than heap
QuickSelect	O(N) avg, O(N²) worst	O(1)	❌ Unstable worst-case

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