Watch 10 video solutions for Kth Largest Element in an Array, a medium level problem involving Array, Divide and Conquer, Sorting. This walkthrough by NeetCode has 331,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4
Constraints:
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104Problem Overview: Given an unsorted integer array nums and an integer k, return the kth largest element in the array. The element is determined by sorted order, but the array itself does not need to be fully sorted.
Approach 1: Sorting the Array (O(n log n) time, O(1) or O(n) space)
The most direct approach sorts the array and returns the element at index n - k. After sorting in ascending order, the kth largest element naturally appears at that position. This uses standard algorithms from sorting. The implementation is simple and reliable, but it performs more work than necessary because it fully sorts the array even though only one position matters. Time complexity is O(n log n), and space complexity depends on the language's sorting implementation (often O(1) or O(n)).
Approach 2: Min-Heap (Priority Queue) (O(n log k) time, O(k) space)
A more efficient method keeps only the top k largest elements using a min-heap. Iterate through the array and push each value into a heap of size at most k. If the heap size exceeds k, remove the smallest element. The heap always stores the current k largest values seen so far, and the root of the heap represents the kth largest element. This approach relies on a heap (priority queue) where insertion and removal take O(log k). After processing all n elements, the total complexity becomes O(n log k) with O(k) extra space. This method works well when k is small compared to n.
Approach 3: Quickselect (Average O(n) time, O(1) space)
Quickselect applies the partitioning idea from Quicksort but focuses only on the side that contains the target index. Convert the problem into finding the element at index n - k in sorted order. Choose a pivot, partition the array so that smaller elements appear on one side and larger elements on the other, and determine which partition contains the target index. Continue the process only on that partition. This divide-and-conquer technique from Quickselect avoids sorting the entire array. The average time complexity is O(n), while the worst case is O(n^2) if poor pivots are consistently chosen. Space complexity is O(1) for the iterative version because the partitioning occurs in-place.
Recommended for interviews: Quickselect is usually the expected optimal solution because it demonstrates understanding of partition-based selection and reduces the average runtime to linear time. The min-heap approach is also widely accepted since it is easy to implement and performs well when k is small. Starting with the sorting solution shows baseline reasoning, but moving quickly to heap or Quickselect signals stronger algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting the Array | O(n log n) | O(1)–O(n) | Simple implementation when performance is not critical |
| Min-Heap (Priority Queue) | O(n log k) | O(k) | Best when k is small relative to n or when streaming data |
| Quickselect | Average O(n), Worst O(n^2) | O(1) | Optimal average performance for selection problems |