K-th Largest Element | Dataford Interview Questions

Glance needs to identify a score threshold for ranking content in a feed. Given an unsorted array of integers nums and an integer k, return the k-th largest element in nums.

The largest element is the 1st largest, and duplicate values count as separate elements. You may modify the input array during processing.

Formal Specification

Input: nums, a non-empty list of integers, and k, a 1-indexed integer.
Output: The integer value that is the k-th largest element of nums.
Requirement: Aim for expected O(n) time and O(1) auxiliary space by using an in-place selection algorithm.

Constraints

1 <= nums.length <= 10^5
1 <= k <= nums.length
-10^9 <= nums[i] <= 10^9
Duplicate values are allowed

Function Signature

def kth_largest(nums, k):

Your question is K-th Largest Element. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem