> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/heap/215.-kth-largest-element-in-an-array.md).

# 215. Kth Largest Element in an Array

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

**Example 1:**

```
Input: [3,2,1,5,6,4] and k = 2
Output: 5
```

**Example 2:**

```
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
```

**Note:** \
You may assume k is always valid, 1 ≤ k ≤ array's length.

```cpp
// HeapSort
// Repeatedly remove the largest element from the heap (the root of the heap), and insert it into the array.
// Heapify procedure can be applied to a node if its children nodes are heapified.
void heapify(vector<int>& nums, int heap_size, int i) { // time: O(nlogn); space: O(1)
    int largest = i;
    int left = 2 * largest + 1, right = 2 * largest + 2;
    if (left < heap_size && nums[left] > nums[largest]) largest = left;
    if (right < heap_size && nums[right] > nums[largest]) largest = right;
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, heap_size, largest); // tail recursion
    }
}
int findKthLargest(vector<int>& nums, int k) {
    int heap_size = nums.size();
    for (int i = heap_size / 2 - 1; i >= 0; --i) {
        heapify(nums, heap_size, i);
    }
    for (int i = 0; i < k; ++i) {
        swap(nums[0], nums[heap_size - 1]);
        --heap_size;
        heapify(nums, heap_size, 0);
    }
    return nums[heap_size];
}
```

```cpp
// STL sort
int findKthLargest(vector<int>& nums, int k) { // time: O(nlogn); space: O(1)
    sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
}
```

```cpp
// Priority_queue
int findKthLargest(vector<int>& nums, int k) { // time: O(nlogk); space: O(k)
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < nums.size(); ++i) {
        pq.push(nums[i]);
        if (pq.size() > k) pq.pop();
    }
    return pq.top();
}
```

```cpp
// Similar QuickSort
int partition(vector<int>& nums, int left, int right) { // time: O(n) for average, O(n^2) for the worst; space: O(1)
    int pivot = nums[left], l = left + 1, r = right;
    while (l <= r) {
        if (nums[l] < pivot && nums[r] > pivot) {
            swap(nums[l++], nums[r--]);
        }
        while (l <= r && nums[l] >= pivot) ++l;
        while (l <= r && nums[r] <= pivot) --r;
    }
    swap(nums[left], nums[r]);
    return r;
}
int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivot_idx = partition(nums, left, right);
        if (pivot_idx == k - 1) return nums[k - 1];
        else if (pivot_idx < k - 1) left = pivot_idx + 1;
        else right = pivot_idx - 1;
    }
}
```

```cpp
// QuickSelect (Randomly choose a pivot)
int partition(vector<int>& nums, int left, int right, int pivot_index) { // time: O(n) for average, O(n^2) for the worst; space: O(1)
    int pivot = nums[pivot_index];
    swap(nums[pivot_index], nums[right]);
    int p_index = left;
    for (int i = left; i < right; ++i) {
        if (nums[i] >= pivot) {
            swap(nums[p_index++], nums[i]);
        }
    }
    swap(nums[p_index], nums[right]);
    return p_index;
}
int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivot_index = left + rand() % (right - left + 1);
        pivot_index = partition(nums, left, right, pivot_index);
        if (pivot_index == k - 1) return nums[k - 1];
        else if (k - 1 < pivot_index) right = pivot_index - 1;
        else left = pivot_index + 1;
    }
}
```

```cpp
// QuickSelect (Choose the right one as a pivot)
int partition(vector<int>& nums, int left, int right) { // time: O(n) for average, O(n^2) for the worst; space: O(1)
    int pivot = nums[right], p_index = left;
    for (int i = left; i < right; ++i) {
        if (nums[i] >= pivot) {
            swap(nums[p_index++], nums[i]);
        }
    }
    swap(nums[p_index], nums[right]);
    return p_index;
}
int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivot_index = partition(nums, left, right);
        if (pivot_index == k - 1) return nums[k - 1];
        else if (k - 1 < pivot_index) right = pivot_index - 1;
        else left = pivot_index + 1;
    }
}
```