215_kth_largest_element.cpp

/*
LeetCode 215 - Kth Largest Element in an Array
Difficulty: Medium

Problem:
Given an integer array nums and an integer k, return the k-th largest element in the array.
Note that it is the k-th largest element in the sorted order, not the k-th distinct element.
Can you solve it without sorting?

Example 1:
    Input: nums = [3,2,1,5,6,4], k = 2
    Output: 5

Example 2:
    Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
    Output: 4

Constraints:
    1 <= k <= nums.length <= 10^5
    -10^4 <= nums[i] <= 10^4

Time Complexity: O(n log k)
Space Complexity: O(k)
*/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // Use a min-heap of size k
        priority_queue<int, vector<int>, greater<int>> min_heap;
        for (int num : nums) {
            min_heap.push(num);
            if (min_heap.size() > k) {
                min_heap.pop();
            }
        }
        return min_heap.top();
    }
};

int main() {
    Solution solution;

    vector<int> nums1 = {3, 2, 1, 5, 6, 4};
    cout << solution.findKthLargest(nums1, 2) << endl;  // 5

    vector<int> nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    cout << solution.findKthLargest(nums2, 4) << endl;  // 4

    return 0;
}