You can refer to the Leetcode problem 215. Kth Largest Element in an Array

#### Problem Statement

Given an integer array `nums`

and an integer `k`

, return the `kth`

largest element in the array.

Note that it is the

`kth`

largest element in the sorted order, not the kth distinct element.

### Example

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

### Approach 1: Using Sorting

We can use sorting to first sort the nums array in natural order and then return kth element from end i.e n-k th element from start.

K index from end is equal to length-k index from start

```
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
```

#### Complexity Analysis

TC: `O(N log N)`

, where `N`

is the size of the input array

SC: `O(1)`

### Approach 2: Using Heap

Actually there are multiple sub-approaches if we choose to use `Heap`

.

Approach | Number of elements | number of poll |
---|---|---|

Min Heap of size N | Min heap to store all N elements(at most `N-K` minimum elements at any given time) |
poll for `N-K` times to get `kth` largest |

Min Heap of size K | Min heap to store at most K elements. Adding new elements after first K elements are added, we check if new element is greater than heap root(peek) and if so we delete it first and then add the new greater element, otherwise not | poll for 1 time and return the polled element |

Max Heap of size N | Max heap to store all N elements(at most `K` maximum elements at any given time) |
poll for `K` times to get `kth` largest |

##### Min Heap of size N

```
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
PriorityQueue<Integer> minHeap = new PriorityQueue();
for(int num: nums){
minHeap.offer(num);
}
int i = 0;
int kThLargest = minHeap.poll();
while (i++ < (n - k)) {
kThLargest = minHeap.poll();
}
return kThLargest;
}
}
```

##### Min Heap of size K

```
import java.util.Arrays;
import java.util.Collections;
//Min Heap of size K
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
PriorityQueue<Integer> minHeap = new PriorityQueue(k);
for(int i=0; i<k; i++){
minHeap.offer(nums[i]);
}
for(int i=k; i<n; i++){
if(minHeap.peek() < nums[i]){
minHeap.poll();
minHeap.offer(nums[i]);
}
}
return minHeap.poll();
}
}
```

##### Max Heap of size N

```
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
if(len == 1){
return nums[0];
}
// Since we are using Max-Heap, we need to sort accordingly
Comparator<Integer> comp = (a,b) -> b.compareTo(a);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(comp);
// Add all the elements
for(int num: nums){
maxHeap.offer(num);
}
// we need to poll for k-1 times and
// return the next polled element
int i = 1;
while(i++ < k){
maxHeap.poll();
}
return maxHeap.poll();
}
}
```

Problem Credit : leetcode.com

## Top comments (0)