Kth Largest Element

Statement

Given an integer array nums and an integer k, return the K-th largest element in the array. Note that it is the K-th largest in sorted order, not the K-th distinct element.

Examples

nums = [3, 2, 1, 5, 6, 4], k = 2
→ 5     (sorted: [1,2,3,4,5,6]; the 2nd largest is 5)

nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
→ 4     (duplicates count separately; the 4th largest in the sorted multiset)

nums = [1], k = 1
→ 1

Constraints

• 1 ≤ k ≤ len(nums) ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴
• Solve in better than O(n log n), sort is the obvious answer; the interview wants you to beat it.

What this problem is really testing

Whether you reach for quickselect when a partial order suffices. Sorting computes more than you need (the full order); quickselect finds the K-th element in expected O(n) by recursing only into the half that contains the answer. Both are standard tools; choosing the right one shows judgment.