kth Largest Element

Problem

Find K-th largest element in an array.

Example

In array [9,3,2,4,8], the 3rd largest element is 4.

In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

Note

You can swap elements in the array

Challenge

O(n) time, O(1) extra memory.

Solution

QuickSelect