Kth Largest Element in an Array

January 4, 2024

Problem # Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example: # Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 Solution # Algorithm: Quickselect This approach is based on the QuickSort algorithm. In QuickSort, we pick a pivot and partition the array around the pivot. The idea of Quickselect is similar, but instead of recursively doing both sides of the pivot, as in QuickSort, Quickselect only recurses into one side – the side with the element it is searching for. ...