Kth Largest Element in an Array
Module 14 · Sorting
Problem
Given an integer array nums and an integer k, return the kth
largest element — the kth largest in sorted order, not the kth
distinct value.
Examples
Example 1
Input
nums = [3,2,1,5,6,4], k = 2Output5Explanation. sorted: [1,2,3,4,5,6]; 2nd largest is 5
Example 2
Input
nums = [3,2,3,1,2,4,5,5,6], k = 4Output4Constraints
1 ≤ k ≤ n ≤ 10⁴.
Attempt it first
The module's capstone: a genuinely surprising result. You do not need to sort the whole array to find one specific rank within it — quicksort's partition step, run just once per level instead of recursing into both sides, finds the kth element in expected linear time. Reason through why before opening the hints; this is the payoff of understanding partition as its own tool, not just sorting's engine.