Kth Largest Element In An Array

Difficulty: Medium Source: NeetCode

Problem

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 sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1: Input: nums = [3, 2, 1, 5, 6, 4], k = 2 Output: 5

Example 2: Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 Output: 4

Constraints:

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Heaps / Priority Queues — min-heap of bounded size
• QuickSelect — partition-based selection algorithm (same idea as quicksort but only recurse on one side)
• Python’s heapq module — heappush, heappop

1. Brute Force — Sort

Intuition

Sort the array in descending order and return the element at index k - 1. Dead simple and fast enough for most practical cases — just not O(n).

Algorithm

1. Sort nums in descending order.
2. Return nums[k - 1].

Solution

def findKthLargest(nums, k):
    nums.sort(reverse=True)
    return nums[k - 1]


print(findKthLargest([3, 2, 1, 5, 6, 4], 2))          # 5
print(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # 4
print(findKthLargest([1], 1))                           # 1

Complexity

• Time: O(n log n)
• Space: O(1) (in-place sort)

2. Min-Heap of Size K

Intuition

Keep a min-heap of exactly k elements. As we stream through nums, if the heap has fewer than k elements we push freely. Once it’s full, only push the new element if it’s larger than the heap’s minimum — and in that case pop the minimum first to keep the heap at size k. At the end, heap[0] is the kth largest.

Algorithm

1. Initialize an empty heap.
2. For each num in nums: a. Push num. b. If len(heap) > k, pop the minimum.
3. Return heap[0].

Solution

import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]


print(findKthLargest([3, 2, 1, 5, 6, 4], 2))          # 5
print(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # 4
print(findKthLargest([1], 1))                           # 1

Complexity

• Time: O(n log k)
• Space: O(k)

3. QuickSelect — O(n) Average

Intuition

QuickSelect is like quicksort, but we only recurse into the partition that contains our target index. We pick a pivot, partition the array so all elements greater than the pivot come first, then check: if the pivot lands at index k - 1 we’re done; otherwise recurse left or right. On average this touches n + n/2 + n/4 + ... ≈ 2n elements.

Algorithm

1. Pick a pivot (we’ll use the last element for simplicity).
2. Partition: move all elements greater than the pivot to the left side. Track the boundary index p.
3. If p == k - 1, return nums[p].
4. If p < k - 1, recurse on the right partition with the same k.
5. If p > k - 1, recurse on the left partition with the same k.

Solution

import random

def findKthLargest(nums, k):
    def quickselect(left, right, k_idx):
        # Randomize pivot to avoid worst-case O(n²)
        pivot_idx = random.randint(left, right)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        pivot = nums[right]

        # Partition: elements > pivot go to the left
        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 == k_idx:
            return nums[p]
        elif p < k_idx:
            return quickselect(p + 1, right, k_idx)
        else:
            return quickselect(left, p - 1, k_idx)

    return quickselect(0, len(nums) - 1, k - 1)


print(findKthLargest([3, 2, 1, 5, 6, 4], 2))          # 5
print(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # 4
print(findKthLargest([1], 1))                           # 1

Complexity

• Time: O(n) average, O(n²) worst case (mitigated by random pivot)
• Space: O(n) worst case recursion stack (use iterative version to get O(1))

Common Pitfalls

Confusing kth largest with kth smallest. The kth largest in a descending sort is at index k - 1, or equivalently the kth smallest in an ascending sort is at index n - k. It’s easy to mix these up — be explicit about your sort direction.

QuickSelect worst case without randomization. A sorted input kills naive QuickSelect when always picking the last element as pivot. Always shuffle or pick a random pivot.

Heap of size k returns heap[0] (the minimum of the top-k). That minimum is the kth largest — not the overall minimum. Students sometimes confuse this and try max(heap) instead.