Kth Largest Element in an Array Solution

Problem

Given an unsorted array of integers, find the element that would appear at position k from the end if the array were sorted in ascending order — or equivalently, the kth largest value counting from the top.

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: Sorted descending gives [6, 5, 4, 3, 2, 1]; the 2nd element is 5.

A second example to clarify the "sorted order, not distinct" rule:

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Explanation: Sorted descending: [6, 5, 5, 4, 3, 3, 2, 2, 1]; the 4th element is 4 (duplicates count as separate positions).

Intuition

The problem asks for the kth position from the right in a sorted array — but you only need one element, not a fully sorted result. A min-heap of size k captures this insight precisely: it always holds the k largest elements seen so far, and its smallest entry (the root) is exactly the kth largest. Quickselect takes a different angle — partition-based selection lets you home in on the answer in O(n) average time by skipping whichever half of the array can't contain it.

Approach 1 — Min-Heap of Size K

Stream through the array, keeping a min-heap that never grows beyond k elements. Whenever the heap exceeds k, evict the smallest. After processing all elements, the heap contains the k largest values and its root is the answer.

Initialize an empty min-heap.
For each number, push it onto the heap.
If the heap size exceeds k, pop the smallest element.
After the loop, return the heap root — it's the smallest of the k largest, which is the kth largest overall.

1import heapq
2
3def findKthLargest(nums: list[int], k: int) -> int:
4    min_heap = []
5    for num in nums:
6        heapq.heappush(min_heap, num)
7        if len(min_heap) > k:
8            heapq.heappop(min_heap)  # evict the current smallest to keep only the top k
9    return min_heap[0]  # smallest of the k largest = kth largest

Time: O(n log k) — each of the n pushes costs O(log k) on a heap bounded to size k.

Space: O(k) — the heap holds at most k+1 elements at any moment.

Approach 2 — Quickselect

Map the problem to a 0-indexed sorted array: the kth largest sits at index n − k in ascending order. Use a partition step (like quicksort's) to place a pivot at its final sorted position. If that position equals n − k, return it. Otherwise recurse only on the side that contains n − k.

Compute targetIndex = n − k.
Choose the rightmost element as the pivot.
Scan left-to-right and move all elements ≤ pivot before a partitionPos pointer.
Swap the pivot into partitionPos — it is now at its correct sorted position.
If partitionPos == targetIndex, return the pivot. Otherwise recurse left or right.

1def findKthLargest(nums: list[int], k: int) -> int:
2    target_index = len(nums) - k  # kth largest sits here in 0-indexed ascending order
3
4    def quickselect(left: int, right: int) -> int:
5        pivot = nums[right]
6        partition_pos = left
7
8        for i in range(left, right):
9            if nums[i] <= pivot:
10                nums[i], nums[partition_pos] = nums[partition_pos], nums[i]
11                partition_pos += 1
12
13        nums[partition_pos], nums[right] = nums[right], nums[partition_pos]
14
15        if partition_pos == target_index:
16            return nums[partition_pos]
17        elif partition_pos < target_index:
18            return quickselect(partition_pos + 1, right)
19        else:
20            return quickselect(left, partition_pos - 1)
21
22    return quickselect(0, len(nums) - 1)

Time: O(n) average — each partition eliminates roughly half the remaining candidates; O(n²) worst-case on adversarial input (always-minimum pivot).

Space: O(log n) average — recursion depth matches the number of partitions until convergence.

Complexity Summary

Approach	Time	Space	When to use
Min-Heap of Size K	O(n log k)	O(k)	When k is small relative to n, or when streaming data without random access
Quickselect	O(n) average / O(n²) worst	O(log n)	When the array fits in memory and you want optimal average performance

Common Mistakes

Using a max-heap of all n elements and popping k times — this costs O(n + k log n): O(n) to heapify, then k pops each at O(log n). The min-heap approach processes each element in O(log k) and never lets the heap grow beyond k, giving O(n log k) total.
Off-by-one in quickselect's target index — "kth largest" maps to index n − k in 0-indexed ascending order, not index k − 1. For n=6, k=2: target is index 4 (the 5th element in [1,2,3,4,5,6]), which is 5. Using k−1=1 would return the 2nd-smallest instead.
Confusing "kth largest" with "kth largest distinct" — for [3, 3, 3, 1] with k=2, the answer is 3 (the 2nd position in [3,3,3,1] sorted descending), not 1 (the 2nd distinct value).
Not randomizing the pivot in quickselect — using the last element as pivot is O(n²) on a sorted or reverse-sorted array. Shuffling the array once before running quickselect, or swapping a random element into the pivot position, restores the O(n) expected cost.
Forgetting that Python's heapq is a min-heap — pushing raw values gives a min-heap by default. For a max-heap you need to negate values (heapq.heappush(heap, -num)) or use a library that supports max-heaps explicitly.

Kth Largest Element in an Array — Solution