> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/heaps-and-priority-queue/215.-kth-largest-element-in-an-array.md).

# 215. Kth Largest Element in an Array

## Problem Statement

<br>

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?

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [3,2,1,5,6,4], k = 2
</strong><strong>Output: 5
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
</strong><strong>Output: 4
</strong></code></pre>

&#x20;

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

### Links

<https://leetcode.com/problems/kth-largest-element-in-an-array/description/>

### Video Links

<https://www.youtube.com/watch?v=XEmy13g1Qxc&ab_channel=NeetCode>

### Approach 1:

```
Priority Queue
```

{% code title="C++" lineNumbers="true" %}

```cpp
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();
    }
};
```

{% endcode %}

### Approach 2:

```
Quick Select
```

{% code title="C++" lineNumbers="true" %}

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

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###