# 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)

```cpp
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)

```cpp
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**

```cpp
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)**