Kth Largest Element in an Array

SortingQuickSelect

MediumLeetCode #215

25 min

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example

Example 1:

nums: [3, 2, 1, 5, 6, 4], k: 2

Output: 5

Explanation: The sorted array is [1, 2, 3, 4, 5, 6]. The 2nd largest element is 5.

Solution

This problem can be solved efficiently using a selection algorithm. A common choice is QuickSelect, which is a modification of the QuickSort algorithm. Its average time complexity is O(n), which is better than sorting the entire array (O(n log n)).

The algorithm works by picking a pivot, partitioning the array around it, and then recursively searching in only one of the partitions based on where the kth largest element would be.

Algorithm Steps (QuickSelect)

First, we convert `k` to be the index we're looking for in a sorted array (`n - k`).
Implement a `quickSelect` function that takes a left and right bound.
Choose a pivot and partition the array. The partition function will place the pivot at its sorted position, `p`.
If `p` is equal to our target index, we've found the element.
If `p` is greater than the target, we only need to search in the left partition.
If `p` is less than the target, we only need to search in the right partition.

QuickSelect Visualization

Ready to start.

Kth Largest Element (QuickSelect)


class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        target_index = len(nums) - k
        
        def quick_select(left, right):
            pivot = nums[right]
            p = left
            
            for i in range(left, right):
                if nums[i] <= pivot:
                    nums[p], nums[i] = nums[i], nums[p]
                    p += 1
            
            nums[p], nums[right] = nums[right], nums[p]
            
            if p > target_index:
                return quick_select(left, p - 1)
            elif p < target_index:
                return quick_select(p + 1, right)
            else:
                return nums[p]

        return quick_select(0, len(nums) - 1)