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, return the kth largest element. The array is not sorted and duplicates may exist. The goal is to identify the element that would appear at position k if the array were sorted in descending order.
Approach 1: Min-Heap (Priority Queue) (Time: O(n log k), Space: O(k))
This approach keeps only the k largest elements seen so far using a min-heap. Iterate through the array and push each number into the heap. If the heap size exceeds k, remove the smallest element using pop(). The heap always contains the top k largest elements, and the root represents the kth largest overall. This method works well when k is much smaller than n and leverages efficient heap operations from a heap (priority queue). The approach is easy to implement and predictable in performance.
Approach 2: Quickselect Algorithm (Average Time: O(n), Worst Case: O(n²), Space: O(1) or O(log n) recursion)
Quickselect is a selection algorithm derived from QuickSort. Instead of fully sorting the array, it repeatedly partitions the array around a pivot. After partitioning, the pivot lands in its correct sorted position. Compare this index with the target index n - k. If they match, you found the kth largest element. Otherwise, recurse into the left or right partition depending on where the target lies. This approach uses the partition idea from divide and conquer and avoids unnecessary sorting work. Average performance is linear, making it one of the fastest practical solutions.
Recommended for interviews: Start by mentioning the heap approach since it is straightforward and guarantees O(n log k) time. Then present Quickselect as the optimal solution with average O(n) time. Interviewers typically expect you to recognize that a full sorting pass (O(n log n)) is unnecessary and that selection algorithms can locate the kth element faster.
By using a Min-Heap, we can efficiently keep track of the k largest elements. Maintain a heap of size k, and for each element in the array, decide whether to add it to the heap. If you add an element to the heap when it is full, remove the minimum element to maintain the size of the heap as k. At the end, the root of the heap will be the kth largest element.
We first define a comparison function cmpfunc that is used by the C library function qsort to sort the array. After sorting, the kth largest element is located at index numsSize - k.
Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation.
Space Complexity: O(1), as we are modifying the input array in-place.
Quickselect is an efficient selection algorithm to find the kth smallest element in an unordered list. The algorithm is related to the quicksort sorting algorithm. It works by partitioning the data, similar to the partitioning step of quicksort, and is based on the idea of reducing the problem size through partitioning.
The quickSelect function recursively partitions the array around pivot elements. The function partition ensures the pivot is in its sorted position with all larger numbers left and smaller numbers right. If the pivot's index equals k, the pivot is the kth largest element. We adjust to 0-based index during each call.
Average-case Time Complexity: O(n), but worst-case O(n²).
Space Complexity: O(1) for iterative solution, O(log n) for recursive calls due to stack depth.
Quick Select is an algorithm for finding the k^{th} largest or smallest element in an unsorted array. Its basic idea is to select a pivot element each time, dividing the array into two parts: one part contains elements smaller than the pivot, and the other part contains elements larger than the pivot. Then, based on the position of the pivot, it decides whether to continue the search on the left or right side until the k^{th} largest element is found.
The time complexity is O(n), and the space complexity is O(log n). Here, n is the length of the array nums.
We can maintain a min heap minQ of size k, and then iterate through the array nums, adding each element to the min heap. When the size of the min heap exceeds k, we pop the top element of the heap. This way, the final k elements in the min heap are the k largest elements in the array, and the top element of the heap is the k^{th} largest element.
The time complexity is O(nlog k), and the space complexity is O(k). Here, n is the length of the array nums.
We can use the idea of counting sort, counting the occurrence of each element in the array nums and recording it in a hash table cnt. Then, we iterate over the elements i from largest to smallest, subtracting the occurrence count cnt[i] each time, until k is less than or equal to 0. At this point, the element i is the k^{th} largest element in the array.
The time complexity is O(n + m), and the space complexity is O(n). Here, n is the length of the array nums, and m is the maximum value among the elements in nums.
| Approach | Complexity |
|---|---|
| Using a Min-Heap (Priority Queue) | Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation. |
| Quickselect Algorithm | Average-case Time Complexity: O(n), but worst-case O(n²). |
| Quick Select | — |
| Priority Queue (Min Heap) | — |
| Counting Sort | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap (Priority Queue) | O(n log k) | O(k) | Best when k is small compared to n and you want predictable performance using heap operations. |
| Quickselect | Average O(n), Worst O(n²) | O(1) iterative or O(log n) recursion | Best for optimal average performance when modifying the array is allowed and full sorting is unnecessary. |
Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 406,270 views views
Watch 9 more video solutions →Practice Kth Largest Element in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor