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.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
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.
| 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²). |
| 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 |
Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,598 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