⚡Flashcard Drill➔
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

  1. A size-k min-heap gives O(n log k), which is simple and usually fast enough.
  2. Quickselect gives O(n) average time: partition around a random pivot and recurse only into the side containing the answer.
  3. The partition places the pivot at its final sorted position, so the index comparison tells you which side to recurse into.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems