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] <= 104The goal of #215 Kth Largest Element in an Array is to find the element that appears in the kth position when the array is ordered from largest to smallest. A straightforward idea is to sort the array and directly access the element at index n - k. While simple, sorting costs O(n log n) time.
A more efficient interview-friendly approach uses a min-heap (priority queue) of size k. By keeping only the largest k elements in the heap, the root always represents the kth largest value. This reduces the time complexity to O(n log k) with O(k) space.
For optimal performance, many candidates use the Quickselect algorithm, a divide-and-conquer technique related to quicksort. It partitions the array around a pivot and recursively focuses only on the relevant side, achieving an average time complexity of O(n) and constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting | O(n log n) | O(1) or O(n) depending on sort |
| Min Heap (size k) | O(n log k) | O(k) |
| Quickselect | Average: O(n), Worst: O(n^2) | O(1) |
NeetCode
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.
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.
1#include <iostream>
2#include <vector>
3#include <queue>
4
5int findKthLargest(std::vector<int>& nums, int k) {
6 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
7 for (int num : nums) {
8 minHeap.push(num);
9 if (minHeap.size() > k) {
10 minHeap.pop();
11 }
12 }
13 return minHeap.top();
14}
int main() {
std::vector<int> nums = {3,2,1,5,6,4};
int k = 2;
std::cout << findKthLargest(nums, k) << std::endl;
return 0;
}We create a min-heap using std::priority_queue by specifying a comparison class std::greater<> to maintain a heap of the k largest elements. By iterating through the elements and maintaining the heap size, the root at the end of the iteration is the kth largest element.
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.
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.
1import
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Quickselect only processes the part of the array that may contain the kth largest element instead of sorting the entire array. This reduces the average time complexity from O(n log n) to O(n).
Yes, this problem is frequently asked in FAANG and other top tech company interviews. It tests knowledge of heaps, partitioning techniques, and algorithm optimization strategies like Quickselect.
A min-heap (priority queue) of size k is commonly used. By maintaining only the top k largest elements, the root of the heap always represents the kth largest value in the array.
The optimal approach is typically Quickselect, which is based on the partition idea from quicksort. It narrows the search space to only the relevant side of the array and achieves O(n) average time complexity, making it very efficient for large inputs.
The Python method takes advantage of Python's dynamic lists and absence of static partitioning constraints. A randomized pivot helps further eliminate edge case pitfalls akin to performance degradation prevalent in non-randomized variants of Quickselect.