1.Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Solution : (using Max Heap)

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

       make_heap(nums.begin(),nums.end());

        int j = 0;
        while (j < k - 1)
        {
            pop_heap(nums.begin(),nums.end());
            nums.pop_back(); 
            j++;
        }

        return nums.front();
    }
};

Time Complexity: O(n + k log(n) ) Heapify takes O(n) and deletion of k elements takes k * log (n)

Solution: (Using Priority Queue)

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

        priority_queue<int, vector<int>> pq(nums.begin(), nums.end());

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

Solution: (Quick Select)

Similar algorithm to quick sort

class Solution
{
public:
    int findPivot(vector<int> &nums, int start, int end)
    {

        int pvt = nums[end];
        int k = start;

        for (int i = start; i < end; i++)
        {
            if (nums[i] < pvt)
            {
                swap(nums[i], nums[k]);
                k++;
            }
        }
        swap(nums[k], nums[end]);
        return k;
    }

    int quickSelect(vector<int> &nums, int start, int end, int k)
    {
        
        if (start > end)
        {
            return -1;
        }

        int p = findPivot(nums, start, end);
        
        if (p == k)
        {
            return p;
        }

        if (p < k)
        {
            return quickSelect(nums, p + 1, end, k);
        }

        else if (p > k)
        {
           return quickSelect(nums, start, p - 1, k);
        }
        
        return -1;
    }
    
    int findKthLargest(vector<int> &nums, int k)
    {
        int n = nums.size();
    
        int res = quickSelect(nums, 0, n - 1, n-k);
        
        return nums[res];

        return res;
    

Time Complexity: O(n)