Kth Largest Element: Heap vs Quickselect

Given an integer array nums and an integer k, return the kth largest element. Not the kth distinct element, but the kth largest in sorted order.

This is LeetCode 215: Kth Largest Element in an Array, and it is a go-to interview question because it has two very different optimal approaches. You can solve it with a min-heap or with quickselect, and interviewers want to see that you understand the tradeoffs between them.

Example: nums = [3, 2, 1, 5, 6, 4], k = 2. The sorted array is [1, 2, 3, 4, 5, 6], so the 2nd largest is 5.

Why this problem matters

Kth largest element shows up constantly as a subproblem. It is the foundation for problems like Top K Frequent Elements, median finding, and stream-based top-k queries. If you can find the kth largest efficiently, you unlock a whole family of problems.

There are three ways to solve it:

1. Sort the array and pick index n - k. O(n log n). Works but not optimal.
2. Min-heap of size k. O(n log k). Clean and practical.
3. Quickselect. O(n) average. Fastest on paper, trickier to implement.

Let's build the heap approach first, then quickselect.

Approach 1: Min-heap of size k

The idea is simple: maintain a min-heap that holds the k largest elements seen so far. As you scan through the array, push each element onto the heap. If the heap grows beyond size k, pop the smallest. When you are done, the smallest element in the heap (the root) is the kth largest overall.

Why does this work? The heap always contains the top k elements. The root is the smallest among those top k, which by definition is the kth largest.

The code

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

Or even shorter using heapq.nlargest:

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]

The explicit version is better for interviews because it shows you understand how the heap works.

Time: O(n log k). Each push/pop is O(log k), and we do it n times.

Space: O(k) for the heap.

When k is small relative to n, this is very efficient. When k is close to n, you might as well sort.

Approach 2: Quickselect

Quickselect is based on the same partition logic as quicksort, but instead of sorting the entire array, it only recurses into the side that contains the target index. On average, this runs in O(n) time.

The idea: pick a pivot, partition the array so that elements smaller than the pivot go left and elements larger go right. After partitioning, the pivot is at its final sorted position. If that position matches your target index, you are done. If the target is to the left, recurse left. If it is to the right, recurse right.

For the kth largest element, the target index (in ascending order) is n - k.

The code

import random

def find_kth_largest(nums: list[int], k: int) -> int:
    target = len(nums) - k

    def quickselect(left: int, right: int) -> int:
        pivot_idx = random.randint(left, right)
        pivot = nums[pivot_idx]

        # Move pivot to the end
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]

        # Partition
        store = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1

        # Put pivot in its final position
        nums[store], nums[right] = nums[right], nums[store]

        if store == target:
            return nums[store]
        elif store < target:
            return quickselect(store + 1, right)
        else:
            return quickselect(left, store - 1)

    return quickselect(0, len(nums) - 1)

Let's break it down:

• Random pivot selection. Picking a random pivot avoids the O(n^2) worst case that comes from always choosing the first or last element. With random pivots, the expected time is O(n).
• Partition. Move everything smaller than the pivot to the left side. After partitioning, the pivot sits at its final sorted position.
• Recurse into one side only. If the pivot's position matches target, return it. Otherwise, recurse into whichever side contains the target. This is what makes quickselect faster than quicksort: you throw away half the array on each pass (on average).

Time: O(n) average, O(n^2) worst case. The average case comes from the geometric series: n + n/2 + n/4 + ... = 2n. The worst case happens if you consistently pick the smallest or largest element as the pivot, but random selection makes this astronomically unlikely.

Space: O(log n) average for the recursion stack. Can be reduced to O(1) with an iterative version.

Heap vs quickselect: which should you use?

Both approaches are valid in an interview. Here is how to decide:

The heap approach is safer for interviews: it has no bad worst case, it does not modify the input, and it generalizes to streaming scenarios (like LeetCode 703: Kth Largest Element in a Stream). Quickselect is faster on average and shows deeper algorithmic knowledge.

If you only have time to learn one, go with the heap. If you want to impress, know both.

Edge cases to watch for

• k = 1. You want the maximum. The heap solution works (heap of size 1). Quickselect also works (target = n - 1).
• k = n. You want the minimum. The heap grows to size n, so it becomes O(n log n). Quickselect targets index 0.
• Duplicates. nums = [3, 3, 3, 3], k = 2. The answer is 3. Both approaches handle this naturally since they do not require distinct elements.
• Single element. nums = [1], k = 1. Return 1. Both approaches work.

The building blocks

This problem uses two core building blocks:

Min-heap of size k

Maintain a heap that holds exactly k elements. Push new elements in, pop the root when the heap exceeds size k. The root is always the smallest of the top k. This is the same building block used in Top K Frequent Elements (where the heap stores frequency-element pairs) and in stream-based problems where you cannot store the full dataset.

The template:

import heapq

heap = []
for item in items:
    heapq.heappush(heap, item)
    if len(heap) > k:
        heapq.heappop(heap)
# heap[0] is the kth largest

Quickselect / partition

Partition an array around a pivot, then recurse into one side. This is the same partition logic used in quicksort, but applied to selection instead of sorting. The building block is the partition function itself: rearrange elements so that everything smaller than the pivot is on the left, everything larger is on the right, and the pivot is in its final sorted position.

def partition(nums, 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

Complexity comparison

Why you will forget this (and how to fix it)

The heap approach is easy to remember because the pattern is mechanical: push, check size, pop if too big. The part you will forget is quickselect. Not the idea (that is intuitive), but the implementation details: where does the pivot go? How does the store pointer work? What do you return when the pivot index matches the target?

These small details are exactly the kind of thing that slips under pressure. Spaced repetition fixes this. You type the partition function from scratch, not from memory of the blog post, but from understanding the invariant: "everything left of store is smaller than the pivot." A few reps at increasing intervals and the implementation becomes muscle memory.

CodeBricks breaks both approaches into separate drills. You practice the heap version and the quickselect version independently, so each building block gets reinforced on its own schedule.

Related posts

• Top K Frequent Elements - Uses the same min-heap-of-size-k building block, combined with frequency counting
• Sliding Window Pattern - Another O(n) technique where you scan through the array maintaining a running state

---

Visual Learner? See how quickselect's partition works with our Quick Sort Visualization — quickselect uses the same partitioning logic.