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.

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 <= 104
• 104 <= nums[i] <= 104

Problem Link

Kth Largest Element in an Array - LeetCode

Video solution

https://www.youtube.com/watch?v=7h1s2SojIRw&t=510s&ab_channel=AbdulBari

Code

/*
Time Complexity:
Best Case : O(n)
Worst Case : O(n*n)
*/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        
        //n-k will be the ideal position of kth greater element in an increasing array
        int n = nums.size();
        return quickSelect(nums,0,nums.size()-1,n-k);
    }
    
    int quickSelect(vector<int>& nums,int low,int high,int pos)
    {
        while(low<high)
        {
            int pivot = findPivot(nums,low,high);
            if(pos>pivot)
                low = pivot+1;
            else if(pos<pivot)
                high = pivot-1;
            
            else
            return nums[pivot];
                
        }
        
        return nums[low];//only one element exists in the input array
    }
    
    int findPivot(vector<int>& nums,int low,int high)
    {
        int pivot = low;
        
        while(low<high)
        {
            //numbers less than equal to pivot will on left of pivot
            while(low<nums.size()&&nums[low]<=nums[pivot])
                low++;
            
            //number greater than pivot will be on right of pivot
            while(high<nums.size()&&nums[high]>nums[pivot])
                high--;
            
            if(low>high)
                break;
            swap(nums[low],nums[high]);
        }
        
        swap(nums[high],nums[pivot]);
        
        return high;
    }
};

Another way

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

        int n = nums.size();
        //n-k will be the ideal position of kth greater element in an increasing array
        k = n-k;
        return quickSelect(nums,0,n-1,k);
}

// here we will be performing partitioning algorithm in which the pivot element selected 
// will be the first element of the array

    int quickSelect(vector<int>& nums, int l,int h,int k) {

        int n = nums.size();
       
        int p = l,i = l, j = h;

        while(i<j) {

            while(i<n && nums[i]<=nums[p]) {
                i++;
            }

            while(j>=0 && nums[j]>nums[p]) {
                j--;
            }

            if(i<j) {
                swap(nums[i],nums[j]);
            }
        }

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

        if(j<k) {
            return quickSelect(nums,j+1, h,k);
        } else if(j>k) {
            return quickSelect(nums,l, j-1,k);
        }

        return nums[j];

    }

};