This content originally appeared on DEV Community and was authored by Ashutosh
Problem
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the
kthlargest 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 kthlargest |
| 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 kthlargest |
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();
}
}
This content originally appeared on DEV Community and was authored by Ashutosh
Ashutosh | Sciencx (2022-04-09T22:09:14+00:00) Kth Largest Element in an Array. Retrieved from https://www.scien.cx/2022/04/09/kth-largest-element-in-an-array/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.