Kth Largest Without Sorting

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Kth Largest Without Sorting. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

Tencent Video analytics may need a ranking threshold from an unsorted batch of engagement scores without fully ordering every score. Given an unsorted integer array and an integer k, return the kth largest element, counting duplicate values as separate elements.

You must not sort the entire array. Modify nums in place if needed, and use an algorithm that achieves average O(n) time.

Formal Specification

Implement find_kth_largest(nums, k):

Input: nums, a mutable list of integers, and k, a 1-based integer rank.
Output: The integer value at rank k when the array is ordered from largest to smallest.
The input array may be rearranged during execution.

Constraints

1 <= len(nums) <= 10^5
1 <= k <= len(nums)
-10^9 <= nums[i] <= 10^9
Duplicate values count as separate elements
The full array must not be sorted

Function Signature

def find_kth_largest(nums, k):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output