Kth Largest Element

Difficulty: Medium · Topic: Sorting

Given an unsorted array nums and an integer k, return the k-th largest element (1-indexed, by sorted order, so duplicates count). Sorting gives an easy O(n log n); a quickselect partition gets the average case to O(n).

Examples

find_kth_largest([3,2,1,5,6,4], 2)
→ 5

Sorted desc: 6,5,… → 2nd is 5.

find_kth_largest([3,2,3,1,2,4,5,5,6], 4)
→ 4

find_kth_largest([1], 1)
→ 1

Target complexity: time O(n log n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.