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)