# Kth Largest Element in an Array

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

#### Approach 1: TreeMap

We can use a `TreeMap` sorted in the descending order of keys to solving the problem. `TreeMap` class extends `AbstractMap` and implements the `NavigableMap` interface.  It creates a map stored in a tree structure.  `TreeMap` is sorted according to the natural ordering of keys or by using an implementation of the `Comparator interface`. Read the following articles to learn more about `TreeMap`. The `TreeMap` will store the array elements in key position sorted in descending order and the value will indicate the number of occurrences of each digit in the array. So we can compare the occurrence count `k` to find the `kth` largest element.

```import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

class TreeMapComparator implements Comparator < Integer > {
// Comparator to sort keys in Descending Order
public int compare(Integer a, Integer b) {
return (b - a);
}
}

class KthLargestSolution {

public int findKthLargest(int[] nums, int k) {
TreeMapComparator tc = new TreeMapComparator();
Map<Integer, Integer> map = new TreeMap<>(tc);
for (int cur: nums) {
int count = map.getOrDefault(cur, 0);
map.put(cur, (count + 1));
}
int i = 0;
int kthLargest = 0;
Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();
for (Map.Entry<Integer,Integer> entry: entrySet) {
i = i + entry.getValue();
if (i == k) {
kthLargest = entry.getKey();
break;
} else if (k < i) {
kthLargest = entry.getKey();
break;
}
}
return kthLargest;
}
}

public class KthLargestElement {

public static void main(String[] args) {
int[] arr = {3,2,3,1,2,4,5,5,6};
KthLargestSolution kthLargestSolution = new KthLargestSolution();
int k = 4;
int kthLargest = kthLargestSolution.findKthLargest(arr, k);
System.out.println("When k = " + k + " || The largest element is :" + kthLargest);
}
}
```

The output of the program is:

`When k = 4 || The largest element is :4`

#### Approach 2: Heap

The idea is to init a heap “the smallest element first”, and add all elements from the array into this heap one by one keeping the size of the heap always less or equal to `k`. That would results in a heap containing `k` largest elements of the array. The head of this heap is the answer, i.e. the kth largest element of the array.

The time complexity of adding an element in a heap of size `k` is `O(logk)`, and we do it `N` times that means `O(Nlogk)` time complexity for the algorithm.

```class Solution {
public int findKthLargest(int[] nums, int k) {

Queue<Integer> minHeap = new PriorityQueue<Integer>
(new Comparator<Integer>(){
public int compare(Integer i1, Integer i2){
return Integer.compare(i1, i2);
}
});

for(int num : nums){
minHeap.offer(num);
if(minHeap.size() > k){
minHeap.poll();
}
}
return minHeap.peek();
}
}
```

Complexity Analysis

• Time Complexity : `O(Nlogk)`.
• Space Complexity : `O(k)` to store the heap elements.

Categories: Heap

Tagged as: ,