Kth Largest Element LeetCode 215 Guide

LeetCode 215 asks you to find the kth largest element in an unsorted integer array. Importantly, "kth largest" means the kth largest in sorted order — not the kth distinct element. For example, given nums = [3, 2, 1, 5, 6, 4] and k = 2, the answer is 5 because sorting descending gives [6, 5, 4, 3, 2, 1] and the second element is 5. If nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4, the answer is 4 — duplicates count as separate positions in the sorted order.

The naive solution sorts the array descending and returns the element at index k-1, running in O(n log n) time. This always works and is a valid interview answer for a first pass, but the follow-up almost always asks if you can do better. There are two better approaches: a min-heap of size k that runs in O(n log k) time with O(k) space, and Quickselect that achieves O(n) average time with O(1) extra space by partitioning in-place.

The problem is a classic selection problem and appears frequently in FAANG interviews precisely because it has multiple solution tiers — O(n log n) sort, O(n log k) heap, and O(n) average Quickselect — and candidates are expected to discuss the trade-offs between them.

The min-heap approach maintains a min-heap of size k as you iterate through the array. For each element, push it onto the heap. If the heap size exceeds k, pop the smallest element. After processing all n elements, the heap contains exactly the k largest elements seen so far, and the top of the heap (the minimum of those k elements) is the kth largest element overall.

This works because the heap invariant ensures that whenever an element is popped, it is smaller than all remaining heap elements. After n elements, the heap holds the k largest values, so its minimum — the heap root — is exactly the kth largest. In Python, heapq is a min-heap by default, so heapq.nlargest(k, nums)[-1] achieves this in one line. In Java, PriorityQueue is a min-heap by default: iterate nums, offer each element, poll if size > k, then peek for the answer.

Time complexity is O(n log k) because each of the n elements may require a heap push and pop, and each heap operation costs O(log k) since the heap never exceeds size k. Space complexity is O(k) for the heap. When k is small relative to n, this is much better than O(n log n) sort. When k ≈ n, the heap degenerates toward O(n log n) and Quickselect becomes preferable.

Quickselect is a selection algorithm derived from Quicksort. The key insight is that Quicksort's partition step places one element — the pivot — in its final sorted position and splits the array into elements less than the pivot and elements greater than the pivot. For finding the kth largest element, you only need to recurse into one of the two halves, not both, reducing the average work from O(n log n) to O(n).

To find the kth largest, reframe it as finding the element at index n-k in the sorted order (0-indexed). Choose a pivot, partition the array so all elements greater than the pivot come before it and all smaller elements come after it, and check where the pivot landed. If the pivot is at index n-k, it is the answer. If the pivot is at an index greater than n-k, recurse into the left subarray. If the pivot is at an index less than n-k, recurse into the right subarray. On average, each partition eliminates half the array, giving a geometric series that sums to O(n).

The partition step itself is O(n) — a single pass through the subarray swapping elements relative to the pivot. Unlike Quicksort, Quickselect never recurses into both halves simultaneously, so average total work is O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n). The space complexity is O(1) extra for an iterative implementation or O(log n) average for a recursive implementation due to the call stack.

The worst case for Quickselect with a fixed pivot (such as always choosing the last element) is O(n^2). This occurs when the array is already sorted or nearly sorted and the pivot consistently lands at one extreme of the partition, reducing the subarray by only one element per step. An array sorted in ascending order with k=1 (find the largest) triggers this worst case if you always pick the last element as pivot.

Randomized pivot selection solves this problem. Before or during each partition step, randomly select a pivot index using a random number generator and swap it with the last element. Because the pivot is uniformly random, the expected partition split is balanced regardless of the input distribution. The expected number of comparisons becomes O(n) regardless of whether the input is sorted, reverse-sorted, or has repeated elements.

In Python, random.randint(left, right) generates a random pivot index within the current subarray bounds. In Java, Random.nextInt(right - left + 1) + left achieves the same. The swap adds O(1) work per partition step and converts the expected time complexity from O(n^2) worst-case to O(n) expected regardless of input, making randomized Quickselect practically superior to the heap approach for large n.

Median of Medians is a deterministic pivot selection strategy that guarantees O(n) worst-case time for Quickselect, eliminating the probabilistic nature of randomized pivot. The algorithm divides the input into groups of 5 elements, finds the median of each group, then recursively finds the median of those medians. This median-of-medians becomes the pivot, guaranteed to be between the 30th and 70th percentile of the array, ensuring the partition eliminates at least 30% of elements each step.

The recurrence for Median of Medians is T(n) ≤ T(n/5) + T(7n/10) + O(n), which resolves to O(n) worst case. The O(n/5) term is the recursive call to find the median of medians on n/5 group medians, T(7n/10) is the recursive Quickselect call on at most 70% of the array, and O(n) is the partition work. This gives O(n) worst case without any randomness.

Despite the theoretical elegance, Median of Medians has a large constant factor — the additional passes to compute group medians add roughly 4-5x the work compared to randomized Quickselect on average inputs. It is rarely used in practice and almost never required in interviews. However, knowing it exists demonstrates thorough understanding of the selection algorithm family and may come up in system design discussions where guaranteed worst-case behavior is required.

Python heap solution: import heapq. def findKthLargest(nums, k): heap = []; for n in nums: heapq.heappush(heap, n); if len(heap) > k: heapq.heappop(heap); return heap[0]. Or more concisely: return heapq.nlargest(k, nums)[-1]. The nlargest shortcut is O(n log k) internally and fine for interviews. Python Quickselect with random pivot: import random. def findKthLargest(nums, k): def partition(left, right): pivot_idx = random.randint(left, right); nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]; pivot = nums[right]; store = left; for i in range(left, right): if nums[i] > pivot: nums[store], nums[i] = nums[i], nums[store]; store += 1; nums[store], nums[right] = nums[right], nums[store]; return store. target = len(nums) - k; left, right = 0, len(nums) - 1; while left < right: idx = partition(left, right); if idx == target: break; elif idx < target: left = idx + 1; else: right = idx - 1; return nums[target].

Java heap solution: public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int n : nums) { pq.offer(n); if (pq.size() > k) pq.poll(); } return pq.peek(); }. Java Quickselect with random pivot: private Random rand = new Random(); public int findKthLargest(int[] nums, int k) { int target = nums.length - k; int left = 0, right = nums.length - 1; while (left < right) { int idx = partition(nums, left, right); if (idx == target) break; else if (idx < target) left = idx + 1; else right = idx - 1; } return nums[target]; } private int partition(int[] nums, int left, int right) { int pivotIdx = left + rand.nextInt(right - left + 1); swap(nums, pivotIdx, right); int pivot = nums[right], store = left; for (int i = left; i < right; i++) if (nums[i] > pivot) swap(nums, store++, i); swap(nums, store, right); return store; }.

Both implementations use the same Lomuto partition scheme where elements greater than the pivot move to the left (since we want descending order for kth largest). The iterative while loop avoids stack overflow on large inputs. The heap approach is simpler and safer for interviews; Quickselect is faster in practice and worth knowing for follow-up discussion.

Top K Frequent Elements (LeetCode 347) extends the selection problem to frequency-based ranking. Instead of the kth largest value, you need the k most frequent values. The approach uses a frequency count map then applies either a max-heap on frequencies (O(n log k)), Quickselect on the unique elements by frequency (O(n) average), or bucket sort where index represents frequency (O(n) guaranteed). Understanding LeetCode 215 Quickselect directly prepares you for LeetCode 347's Quickselect variant.

K Closest Points to Origin (LeetCode 973) is another selection problem: find the k points closest to (0, 0) by Euclidean distance. The solution structure is identical — min-heap of size k (O(n log k)) or Quickselect by distance (O(n) average). Find Median from Data Stream (LeetCode 295) extends heap usage to maintain two heaps (max-heap for lower half, min-heap for upper half) so the median is always accessible in O(1) after O(log n) inserts.

The broader selection algorithm family — Quickselect, Median of Medians, heap-based selection — forms a core topic in algorithm courses and competitive programming. Order statistics trees (augmented BSTs) solve selection in O(log n) with O(n) space and support dynamic insertions and deletions, making them the right tool when the array changes over time. For static arrays and one-time queries, randomized Quickselect remains the practical champion.