# Kth Largest Element in an Array

## Challenge Description

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:

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

## Approach #1: Sort the array and get by index

Time complexity is O(NlogN), a flaw is we modified the original array.

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

## Approach #2: Use heak minheap with size K

If we initialize a minheap with size of K, the top value is what we want.

For minheap, the insertion operation has a worst-case time complexity of O(logN) but an average-case complexity of O(1).

So we have a overall average-case complexity of O(N) and worst time complexity O(NlogN).

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

## Approach #3: Divide and conquer

Just like quick sort, we use a `partition` function to split array into two parts, the left part of elements are all less than `pivot`, the right part of elements are all greater than `pivot`.

And reduce the search range in every iteration.

Overall time complexity O(N).

``````class Solution {

private:
void swap(vector<int>& a, int x, int y) {
int t = a[y];
a[y] = a[x];
a[x] = t;
}

int random(int a, int b) {
return (int) (rand() % (b - a + 1)) + a;
}

int partition(vector<int>& nums, int left, int right, int index) {
int pivot = nums[index];
swap(nums, index, right);
int i = left - 1;
for (int j=left; j<=right-1; j++)
if (nums[j] <= pivot)
swap(nums, ++i, j);
swap(nums, right, i+1);
return i+1;
}

int quick_select(vector<int>& nums, int left, int right, int k) {
while (left <= right) {
int pivot = partition(nums, left, right, random(left, right));
if (pivot == k) return nums[k];
else if (k > pivot) left = pivot + 1;
else right = pivot - 1;
}
return -1;
}

public:
int findKthLargest(vector<int>& nums, int k) {
return quick_select(nums, 0, nums.size() - 1, nums.size() - k);
}
};
``````
Last Updated on