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.

Note that it is the kth largest element in the sorted order, not the kth 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 <= 105
-104 <= nums[i] <= 104

Intuition

Approach 1:
Use heap to store the elements and pop the kth element from the top

Approach 2:
Using the Quick select algorithm: Partition algorithm
Run the partition algorithm and find if the pivot index is indeed we are looking for
Else run on the other half

Video Links

Approach 1:

Priority Queue

C++

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int>pq;

        for (int i = 0; i < nums.size(); i++){
            pq.push(nums[i]);
        }

        for(int i = 0; i < k-1; i++) {
            pq.pop();
        }

        return pq.top();
    }
};

Approach 2:

Quick Select

C++

class Solution {
public:
    int quickSelect(vector<int>& nums, int index, int left, int right){
        int pivot = nums[right];
        int j=left;

        for(int i=left; i<right; i++){
            if(nums[i] <= pivot){
                swap(nums[j++], nums[i]);  
            }
        }

        swap( nums[j], nums[right]);

        if(j == index)
            return nums[j];

        else if(j < index)
            return quickSelect(nums, index, j+1, right);

        return quickSelect(nums, index, left, j-1);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int index = n-k;

        return quickSelect(nums, index, 0, n-1);
    }
};

Approach 3:

C++

Approach 4:

C++