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