Skip to main content

Kth Largest Element in an Array (LeetCode)

Problem Description​

Problem StatementSolution LinkLeetCode Profile
Kth Largest Element in an ArrayKth Largest Element in an Array Solution on LeetCodevaishu_1904

Problem Description​

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 sorted order, not the kth distinct element.

Examples​

Example 1​

  • Input: nums = [3,2,1,5,6,4], k = 2
  • Output: 5
  • Explanation: The second largest element is 5.

Example 2​

  • Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
  • Output: 4
  • Explanation: The fourth largest element is 4.

Constraints​

  • 1 <= k <= nums.length <= 10^4
  • −104<=nums[i]<=104-10^4 <= nums[i] <= 10^4

Approach​

To find the kth largest element in an unsorted array, we can use various methods such as sorting, using a min-heap, or using Quickselect algorithm. Here are the approaches:

  1. Sorting:

    • Sort the array and return the element at index len(nums) - k.
  2. Min-Heap:

    • Maintain a min-heap of size k.
    • Iterate through the array and maintain the heap with the largest k elements.
    • The root of the heap will be the kth largest element.
  3. Quickselect:

    • Use a partition-based method to find the kth largest element in O(n) average time complexity.

Solution Code​

Python​

import heapq

class Solution:
def findKthLargest(self, nums, k):
return heapq.nlargest(k, nums)[-1]

Java​

import java.util.PriorityQueue;

class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}

C++​

#include <queue>
#include <vector>

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num : nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop();
}
}
return minHeap.top();
}
};

Conclusion​

The above solutions effectively find the kth largest element in an array using different methods. The min-heap approach provides an efficient solution with a time complexity of O(n log k), making it suitable for larger inputs while ensuring the correct element is found. Each implementation handles edge cases and constraints effectively, providing robust solutions across various programming languages.