class Solution {
public:
    // Run-time complexity O(max(n, klogn))
    // Memory complexity O(n)
    /*
    int findKthLargest(vector<int>& nums, int k) {

        // O(n)
        priority_queue<int> pq_nums(nums.begin(), nums.end());

        // O(klogn)
        for (int i = 0; i < k - 1; ++i)
            pq_nums.pop();

        return pq_nums.top();
    }
    */

    // Run-time complexity O(max(k, (n-k)logk))
    // Memory complexity O(k)
    int findKthLargest(vector<int>& nums, int k) {

        // O(k)
        priority_queue<int, vector<int>, greater<int>> pq_nums(nums.begin(), nums.begin() + k);

        // O((n-k)logk)
        for (int i = k; i < nums.size(); ++i) {
            if (nums[i] > pq_nums.top()) {
                pq_nums.pop();
                pq_nums.push(nums[i]);
            }
        }

        return pq_nums.top();
    }

};