MediumBlind75ArrayHeapDivide and Conquer
Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Examples
Input
nums = [3,2,1,5,6,4], k = 2
Output
5
The 2nd largest element is 5.
Input
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output
4
The 4th largest element is 4.
Constraints
- •
1 <= k <= nums.length <= 10^5 - •
-10^4 <= nums[i] <= 10^4
Approaches
Sort the array in descending order and return the kth element.
CodeT: O(n log n) | S: O(1)
def find_kth_largest(nums, k):
nums.sort(reverse=True)
return nums[k-1]Maintain a min heap of size k. The root is the kth largest.
CodeT: O(n log k) | S: O(k)
import heapq
def find_kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]Use the quickselect algorithm to find the kth largest in average O(n).
Diagram
nums = [3,2,1,5,6,4], k=2
Find 2nd largest = (n-k)th smallest = 4th smallest
Quickselect partitions until pivot is at index 4
Result: 5
CodeT: O(n) average | S: O(1)
import random
def find_kth_largest(nums, k):
def quickselect(left, right, k_smallest):
if left == right:
return nums[left]
pivot_idx = random.randint(left, right)
pivot_idx = partition(left, right, pivot_idx)
if k_smallest == pivot_idx:
return nums[k_smallest]
elif k_smallest < pivot_idx:
return quickselect(left, pivot_idx - 1, k_smallest)
else:
return quickselect(pivot_idx + 1, right, k_smallest)
def partition(left, right, pivot_idx):
pivot = nums[pivot_idx]
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
store = left
for i in range(left, right):
if nums[i] < pivot:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[right] = nums[right], nums[store]
return store
return quickselect(0, len(nums) - 1, len(nums) - k)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Sorting | O(n log n) | O(1) | Sort the array in descending order and return the kth element. |
| Min Heap of Size k | O(n log k) | O(k) | Maintain a min heap of size k. The root is the kth largest. |
| Quickselect | O(n) average | O(1) | Use the quickselect algorithm to find the kth largest in average O(n). |
Sorting
T: O(n log n)S: O(1)
Sort the array in descending order and return the kth element.
Min Heap of Size k
T: O(n log k)S: O(k)
Maintain a min heap of size k. The root is the kth largest.
Quickselect
T: O(n) averageS: O(1)
Use the quickselect algorithm to find the kth largest in average O(n).
Common Mistakes
Using a max heap when a min heap of size k is more efficient
Not handling duplicate elements correctly
Forgetting that quickselect has O(n^2) worst case