An Interest In:
Web News this Week
- April 27, 2024
- April 26, 2024
- April 25, 2024
- April 24, 2024
- April 23, 2024
- April 22, 2024
- April 21, 2024
April 9, 2022 10:09 pm GMT
Original Link: https://dev.to/metaverse/kth-largest-element-in-an-array-507c
Kth Largest Element in an Array
Problem
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 = 2Output: 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 Kclass 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(); }}
Original Link: https://dev.to/metaverse/kth-largest-element-in-an-array-507c
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To