LeetCode 215 · Heap / Priority Queue · concepts: heaps, searching

Problem

Return the k-th largest element in an unsorted array (the k-th in sorted-descending order, not the k-th distinct).

[3,2,1,5,6,4], k=2  ->  5

Approach 1 — heap

A size-k min-heap gives O(n log k); or heapq.nlargest(k, nums)[-1]. Reliable, easy.

Approach 2 — Quickselect (optimal average)

Quickselect is quicksort’s partition without the full recursion: pick a pivot, partition so smaller elements go one side and larger the other, and recurse into only the side containing the target rank. It reaches the k-th element in O(n) average.

import random
 
def findKthLargest(nums, k):
    target = len(nums) - k                  # k-th largest = index (n-k) in ascending order
    def quickselect(l, r):
        pivot = nums[random.randint(l, r)]
        # 3-way partition into < pivot, == pivot, > pivot
        lt = [x for x in nums[l:r+1] if x < pivot]
        eq = [x for x in nums[l:r+1] if x == pivot]
        gt = [x for x in nums[l:r+1] if x > pivot]
        if target < l + len(lt):
            return quickselect(l, l + len(lt) - 1)
        elif target < l + len(lt) + len(eq):
            return pivot                    # target lands in the pivot block
        else:
            return quickselect(l + len(lt) + len(eq), r)
    return quickselect(0, len(nums) - 1)

Time O(n) average, O(n²) worst (mitigated by a random pivot); space O(n) here (in-place partitioning gets O(1)).

Heap vs Quickselect

HeapQuickselect
TimeO(n log k)O(n) avg, O(n²) worst
SpaceO(k)O(1) in-place
Streaming inputyesno (needs all data)
Stable / simplesimplertrickier, has worst case

Key insight

Selection (k-th order statistic) doesn’t need a full sort — partition toward the target rank (Quickselect), or bound a size-k heap. Random pivoting keeps Quickselect near-linear; the heap wins when data streams in.

↑ Back to NeetCode 150 — Solved