# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/heap/215.-kth-largest-element-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.