Kth Largest Element in an Array
Tags: leetcode, array, heap, algorithms
Published: 2022-04-09 22:09:14


You can refer to the Leetcode problem [215. Kth Largest Element in an Array](https://leetcode.com/problems/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
```shell
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

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

```java
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
```Java
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](https://leetcode.com)