Kth Largest Element in an Array

Heaps & Top-K, problem 3 of 7

Kth Largest Element in an Array

Medium

LC #215

min-heaptop-kquickselect

Not attempted yet

Given an integer list nums and an integer k, return the k-th largest element in sorted order (duplicates count, so it is not the k-th distinct value).

Try to beat sorting the whole list.

Example 1

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Sorted descending: 6, 5, 5, 4, ... the 4th is 4.

Constraints

  • 1 <= k <= len(nums) <= 10^5
  • -10^5 <= nums[i] <= 10^5

Python

Loading draft…

Test results

7 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

2 examples, 5 hidden

Run examples, then submit all tests.