Hints — p41 Kth Largest Element

Hint 1. There are at least THREE acceptable solutions: sort (O(n log n)), heap (O(n log K)), quickselect (O(n) expected). Name all three; pick deliberately. Don’t just say “sort it.”

Hint 2. Heap approach: to find the K LARGEST, use a MIN-heap of size K. The root is the smallest of the K largest seen so far — i.e., the current candidate for K-th largest.

heap = []
for x in nums:
    if len(heap) < k: heappush(heap, x)
    elif x > heap[0]: heappushpop(heap, x)
return heap[0]

heappushpop is one atomic O(log K) op (faster than push then pop).

Hint 3. Quickselect: recurse into ONE side of a partition. Target index n - k (0-indexed in ascending order).

pivot = random.choice(arr)  # RANDOMIZE
lows = [x < pivot]; eqs = [x == pivot]; his = [x > pivot]
if target < len(lows): recurse(lows, target)
elif target < len(lows)+len(eqs): return pivot
else: recurse(his, target - len(lows) - len(eqs))

The 3-way split is essential — handles duplicates without quadratic blowup.

Hint 4. Random pivot is non-negotiable. nums[0] or nums[-1] as pivot degrades to O(n²) on sorted/reverse-sorted input. Adversarial DoS risk in production.

Hint 5. Streaming follow-up (LC 703): heap-of-size-K is the ONLY answer — quickselect needs the full array. Class supports add(val) returning current K-th largest.

If still stuck: see solution.py.