NeetCode #532LC-215MediumHeap / Priority QueueNC 150NC 250
← Back to All Problems#532 · #215 · Kth Largest Element in an Array(数组中的第 K 个最大元素)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return the k-th largest element. Constraints: 1 <= k <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4. The follow-up asks for O(n) average time.💡 Core Algorithmic Approaches
- A size-
kmin-heap gives O(n log k), which is simple and usually fast enough. - Quickselect gives O(n) average time: partition around a random pivot and recurse only into the side containing the answer.
- The partition places the pivot at its final sorted position, so the index comparison tells you which side to recurse into.
- Randomising the pivot is essential to avoid the O(n^2) worst case on sorted input.
💻 Benchmark Python3 Implementation
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
import heapq
# a size-k min-heap of the k largest values; the root is the answer
return heapq.nlargest(k, nums)[-1]
# Quickselect: O(n) average, O(n^2) worst case without randomisation
class Solution2:
def findKthLargest(self, nums: List[int], k: int) -> int:
import random
target = len(nums) - k # index in ascending order
def quickselect(lo: int, hi: int) -> int:
pivot = nums[random.randint(lo, hi)]
i, j = lo, hi
while i <= j:
while nums[i] < pivot:
i += 1
while nums[j] > pivot:
j -= 1
if i <= j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
if target <= j:
return quickselect(lo, j)
if target >= i:
return quickselect(i, hi)
return nums[target] # the pivot landed exactly on the target
return quickselect(0, len(nums) - 1)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log k) for the heap version, O(n) average for quickselect (O(n^2) worst case without randomisation).
💾 Space Complexity
O(k) for the heap, O(log n) recursion for quickselect.
⚠️ Interview Pitfalls & Follow-ups
- Using
nums.sort(): O(n log n) and it mutates the input. - Confusing the k-th largest with the k-th smallest: the target index is
len(nums) - k. - Choosing the first element as the pivot: sorted input degrades quickselect to O(n^2).
- Recursing into both partitions: only one side contains the answer, so the other must be discarded -- that is what gives the linear average time.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.