Kth Largest Element

medium

Find the kth largest element using QuickSelect (partition)

Kth Largest (QuickSelect)

Key Insight

Partition once, then only recurse into the side containing the target index

Step 1Setup
k=2, target index = 6-2 = 4
3
0
2
1
1
2
5
3
6
4
4
5

Find 2nd largest in [3, 2, 1, 5, 6, 4]. That's index 4 in sorted order.

1 / 4

Learn the Pattern

SortingUse sorting as a preprocessing step to simplify problems, or apply partition logic for in-place rearrangement. Many interview problems become trivial once the array is sorted.
HeapUse a heap (priority queue) when you repeatedly need the minimum or maximum of a changing set while also inserting and deleting values efficiently.
Practice the Code

Step-by-Step Walkthrough: Kth Largest (QuickSelect)

Partition once, then only recurse into the side containing the target index

  1. Setup

    Find 2nd largest in [3, 2, 1, 5, 6, 4]. That's index 4 in sorted order.

  2. First Partition (pivot=4)

    Partition around 4. Elements < 4 go left, ≥ 4 go right.

  3. Recurse Right [6, 5]

    Only search [6, 5]. Partition around 5.

  4. Found!

    Pivot landed at index 4 = our target. The 2nd largest is 5.