Kth Largest via Quickselect

Problem

Return the k-th largest element (1-indexed) of nums using quickselect.

Partition around the last element and recurse only into the side containing the target index len(nums) - k, giving average O(n) time. Duplicates are allowed and the input may contain negatives.

Hint

The k-th largest sits at sorted index len(nums) - k.

Test cases

case 1

in: [[3,2,1,5,6,4],2]

expected: 5

case 2

in: [[3,2,3,1,2,4,5,5,6],4]

expected: 4

case 3

in: [[1],1]

expected: 1

case 4

in: [[7,7,7],2]

expected: 7

case 5

in: [[-1,-2,-3],1]

expected: -1

Starter codePython

def kth_largest_quickselect(nums, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor