Medium

Kth Largest Element in an Array

038

Return the kth largest value in nums.

EXAMPLES

Example 1

Input
{
  "nums": [
    3,
    2,
    1,
    5,
    6,
    4
  ],
  "k": 2
}

Output
5

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

Quick select partitions the array around a pivot and recurses on only one side based on k's position relative to the partition.

Reveal reference solution +

pythonREFERENCE

# Solution 1: Sort
def findKthLargest(self, nums: List[int], k: int) -> int:
    nums.sort()
    return nums[-k]

# Solution 2: Min heap of size k
def findKthLargest(self, nums: List[int], k: int) -> int:
    heap = []
    for num in nums:
        heappush(heap, num)
        if len(heap) == k + 1:
            heappop(heap)
    return heap[0]

# Solution 3: Quick Select (O(n) average)
def findKthLargest(self, nums: List[int], k: int) -> int:
    if not nums:
        return
    pivot = random.choice(nums)
    left = [x for x in nums if x > pivot]
    mid = [x for x in nums if x == pivot]
    right = [x for x in nums if x < pivot]

    L, M = len(left), len(mid)

    if k <= L:
        return self.findKthLargest(left, k)
    elif k > L + M:
        return self.findKthLargest(right, k - L - M)
    else:
        return mid[0]

TimeO(n) average for quickselect

SpaceO(n)

Open on LeetCode ↗