FAANG · LeetCode #215

Kth Largest Element in an Array — three-stage drill

1The ProblemMedium

Kth Largest Element in an Array

Given an unsorted array, find the value that would sit at position k if it were sorted descending.

Examples

nums=[3,2,1,5,6,4], k=2→ 5nums=[3,2,3,1,2,4,5,5,6], k=4→ 4

constraint1 ≤ k ≤ nums.length. Solution uses O(n log k) time, O(k) space — better than the naïve sort's O(n log n) when k is small.

2The PatternTIME O(n log k) · SPACE O(k)

Heap / Top-K

A heap keeps one extreme on top: a max-heap the largest, a min-heap the smallest. Inserting bubbles the new item up until the heap order holds — toggle to compare the two.

Problems using this pattern

3The SolutionRESULT → 5

Step through it

given nums of length 6, k = 2 · find the 2nd largest

Step 1 / 21

Python▎hand-rolled min-heap · sift_up on push · sift_down on replace · top is answer

1def findKthLargest(nums, k):
2    heap = []                                  # hand-rolled MIN-heap: heap[0] is the smallest
3 
4    def sift_up(i):                            # bubble heap[i] up while smaller than its parent
5        while i > 0:
6            parent = (i - 1) // 2
7            if heap[parent] <= heap[i]:        # parent already ≤ child → heap order holds
8                break
9            heap[parent], heap[i] = heap[i], heap[parent]
10            i = parent
11 
12    def sift_down(i):                          # push heap[i] down while a child is smaller
13        n = len(heap)
14        while True:
15            small, l, r = i, 2 * i + 1, 2 * i + 2
16            if l < n and heap[l] < heap[small]: small = l
17            if r < n and heap[r] < heap[small]: small = r
18            if small == i:                     # no smaller child → settled
19                break
20            heap[i], heap[small] = heap[small], heap[i]
21            i = small
22 
23    for x in nums:
24        if len(heap) < k:                      # push: append at the leaf, sift up
25            heap.append(x)
26            sift_up(len(heap) - 1)
27        elif x > heap[0]:                      # replace: overwrite root, sift down
28            heap[0] = x
29            sift_down(0)
30        # else: discard — can't be in the top k
31 
32    return heap[0]                             # smallest of the k survivors → kth largest

why it worksSweep nums once with a MIN-heap of capacity k. Here the heap is written out by hand so the mechanics the viz animates are visible: sift_up bubbles a freshly pushed value up while it's smaller than its parent (keeping the smallest on top); sift_down pushes a value down while a child is smaller (restoring the root after a replace). While the heap isn't full, push. Once full, compare each new x against heap[0] (the smallest of the current top-k): if x is bigger it deserves a slot — overwrite the root and sift down. If x ≤ heap[0], discard it. At the end heap[0] is the kth largest, since the heap holds exactly the k biggest values seen and the root of a min-heap is the smallest of them. (Python's heapq would do all this for you — it's always a min-heap.) O(n log k) time, O(k) space — beats sort when k is small.

Kth Largest Element in an Array — three-stage drill