Kth Largest Element in an Array
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 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] <= 104
Solve it on LeetCode
Approaches
1. Basic Approach: Sorting
Intuition:
The simplest and most direct way to find the k-th largest element is to sort the array first. Once sorted, the k-th largest can be easily accessed by indexing.
Approach:
- Sort the entire array in descending order.
- Retrieve the k-th element from the sorted array.
Code:
- Time Complexity: O(n log n) due to the sorting step.
- Space Complexity: O(1) if we sort in-place; otherwise, O(n) if we use additional space to store a sorted copy.
2. Min-Heap Approach
Intuition:
Instead of sorting the entire array, we can use a min-heap to maintain the k largest elements and efficiently find the k-th largest.
Approach:
- Create a min-heap of size k.
- Iterate through each element of the array.
- If the heap size is less than k, add the element to the heap.
- Else if the current element is larger than the smallest element in the heap, replace the smallest.
- The top of the heap will be the k-th largest element.
Code:
- Time Complexity: O(n log k), where n is the number of elements, as each insertion into the heap takes O(log k).
- Space Complexity: O(k) for the heap storing k elements.
3. Quickselect (Optimal)
Intuition:
Quickselect is a selection algorithm to find the k-th smallest element in an unordered list. It is based on the QuickSort algorithm. Instead of recursing both sides of the pivot, we only recurse into the part that contains the k-th element.
Approach:
- Use a partition method to place the pivot at its correct position in a sorted array.
- If the pivot is at index
n-k, return its value. - Otherwise, recurse on the subarray containing the k-th largest element.
Code:
- Time Complexity: O(n) on average, O(n^2) in the worst case due to the pivot choice.
- Space Complexity: O(1) since we perform in-place partitioning.