215. Kth Largest Element in an Array Leetcode Solution
Kth Largest Element in an Array Leetcode 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.
Can you solve it without sorting?
Kth Largest Element in an Array Leetcode Solution :
Constraints :
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Example 1:
- Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
- Output: 4
Intuition :
The intuition for arriving at this solution is grounded in the properties of a max heap (priority queue) and the goal of efficiently finding the kth largest element in an array.
Approach :
Priority Queue (Max Heap): The priority_queue in C++ is implemented as a max heap, which means that the element with the highest value will always be at the top of the heap. This is useful for finding the kth largest element because we want to keep track of the largest elements while discarding the smaller ones.
Initialization: The priority queue is initialized with the elements from the nums vector. This will automatically build the max heap, with the largest element at the top.
Adjusting k: Since we’re interested in finding the kth largest element, we need to adjust the value of k by subtracting 1. This is because the top element of the max heap is the 1st largest element, the next top element will be the 2nd largest, and so on.
Loop to Pop Elements: The loop iterates k times, and in each iteration, it removes the top element (the largest element) from the priority queue using pq.pop(). This effectively removes the k-1 largest elements from the heap.
Returning Result: After the loop, the priority queue will only contain the kth largest element (since k-1 larger elements have been removed), and this element is returned as the result.
In summary, this code leverages the properties of a max heap (implemented as a priority queue) to find the kth largest element efficiently. By removing the top element (the largest) k-1 times, the code isolates and returns the kth largest element remaining in the heap. This approach ensures that we don’t need to sort the entire array, making the solution more efficient, especially for large arrays.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int findKthLargest(vector< int>& nums, int k) {
priority_queue< int> pq(nums.begin(),nums.end());
k -= 1;
while(k--){
int ele = pq.top();
pq.pop();
}
return pq.top();
}
};
class Solution {
public int findKthLargest(int[] nums, int k) {
quickSelect(nums, 0, nums.length - 1, k - 1);
return nums[k - 1];
}
Random r = new Random();
private int[] pivot(int[] nums, int start, int end) {
int idx = start + r.nextInt(end - start + 1);
int pivoted = nums[idx];
int i = start, j = start, k = end;
while (j <= k) {
if (nums[j] > pivoted) {
swap(nums, i, j);
i++;
j++;
} else if (nums[j] == pivoted) {
j++;
} else {
swap(nums, j, k);
k--;
}
}
return new int[]{i, j};
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
return;
}
private void quickSelect(int[] nums, int start, int end, int k) {
if (start > end) {
return;
}
int[] pivotRes = pivot(nums, start, end);
if (k >= pivotRes[0] && k < pivotRes[1]) {
return;
}
if (k < pivotRes[0]) {
quickSelect(nums, start, pivotRes[0] - 1, k);
} else {
quickSelect(nums, pivotRes[1], end, k);
}
}
}
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
pivot=random.choice(nums)
left=[x for x in nums if x>pivot]
mid=[x for x in nums if x==pivot]
right=[x for x in nums if x< pivot]
n=len(left)
m=len(mid)
if k<=n:
return self.findKthLargest(left,k)
elif k>(n+m):
return self.findKthLargest(right,k-(n+m))
else:
return mid[0] Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment