> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_215.md).

# leetcode\_215

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

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

## Solutions

1. **brute force  O(nlog(n))  S(1)**
2. sorting

```cpp
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};
```

1. **quick sort based partition  O(n) S(1)**
2. time complexity: O(n) + O(n/2) + O(n/4)... worst case: O(n2)

```cpp
#include <experimental/random>
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // k largest equals to size - k smallest
        k = nums.size() - k;
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            // use random to prevent deterioration of complexity to O(n2)
            swap(nums[lo], nums[std::experimental::randint(lo, hi)]);
            // be carefull, the pivot is not nums[0]
            int pivot = nums[lo];
            int i = lo, j = hi;
            while (i < j) {
                while (i < j && nums[j] >= pivot) j--;
                nums[i] = nums[j];
                while (i < j && nums[i] <= pivot) i++;
                nums[j] = nums[i];
            }
            nums[i] = pivot;
            // you can also check if i equals k
            if (i <= k) lo = i + 1;
            if (i >= k) hi = i - 1;
        }

        return nums[k];
    }
};
```

1. **heap O(n) + nlog(k)  S(k)**
2. Maintaing a min heap with k largest elements.
3. Other heap based selection algorithm also works.

```cpp
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>>  heap;
        for (int i = 0; i < k; i++)
            heap.push(nums[i]);
        for (int i = k; i < nums.size(); i++) {
            heap.push(nums[i]);
            heap.pop();
        }

        return heap.top();
    }
};
```

Or a manually built heap.

```cpp
```

1. **bucket sort O(n) S(max - min + 1)**
2. reference: <https://leetcode-cn.com/problems/kth-largest-element-in-an-array/comments/105522>

```cpp
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        auto min_max = minmax_element(nums.begin(), nums.end());
        int min = *min_max.first, max = *min_max.second;
        vector<int> bucket(max - min + 1, 0);
        for (auto & num : nums)
            bucket[num - min]++;
        int count = 0;
        for (int i = max - min; i >= 0; i--) {
            count += bucket[i];
            if (count >= k)
                return min + i;
        }
        return -1;
    }
};
```

1. **Iteratively remove the smallest element  O(kn) S(k)**
2. reference: <https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/>
3. The complexity equals to iteratively find the largest element k times.

```cpp
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        vector<int> store(nums.begin(), nums.begin() + k);
        auto pmin =  min_element(store.begin(), store.end());

        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > *pmin) {
                *pmin = nums[i];
                pmin = min_element(store.begin(), store.end());
            }
        }
        return *pmin;
    }
};
```

1. **introselect**
2. **binary search**
3. Speculate the target number in the range of 32bit interger by counting the number of elements slower than it. For the target k'th larget number, numbers in the array <= it should be at least k.

```cpp
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if (k > nums.size()) return -1;
        k = nums.size() - k + 1;
        long lo = INT_MIN, hi = INT_MAX;
        while (lo < hi) {
            long mid = lo + ((hi - lo) >> 1);
            int less = 0;
            for (auto n : nums) less += n <= mid;
            // for the target, numbers less(<=) should be at least k(may have duplicates).
            // if not satisfy, we can ensure the target is at least mid + 1
            if (less < k)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_215.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.