Skip to main content

215 - Kth Largest Element in an Array

Difficulty: Medium | Pattern: Heap / QuickSelect | Company tags: Amazon, Facebook, Google, Microsoft

Problem Statement​

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

Note that it is the k-th largest element in sorted order, not the k-th 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

Approach 1: Min-Heap of Size k — O(n log k)​

Key insight: Maintain a min-heap of size k. When the heap grows beyond k, pop the smallest. At the end, the heap's minimum is the k-th largest overall.

import heapq

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

Approach 2: QuickSelect — O(n) average​

Key insight: Like QuickSort's partition, but only recurse into the side containing the k-th largest. Average O(n), worst case O(n²).

import random

def findKthLargest(nums: list[int], k: int) -> int:
    target = len(nums) - k  # k-th largest = (n-k)-th smallest (0-indexed)
    
    def quickselect(left, right):
        pivot = nums[right]
        p = left
        for i in range(left, right):
            if nums[i] <= pivot:
                nums[i], nums[p] = nums[p], nums[i]
                p += 1
        nums[p], nums[right] = nums[right], nums[p]
        
        if p == target:
            return nums[p]
        elif p < target:
            return quickselect(p + 1, right)
        else:
            return quickselect(left, p - 1)
    
    random.shuffle(nums)  # prevent worst case
    return quickselect(0, len(nums) - 1)

Approach 3: Python Built-in — O(n)​

import heapq

def findKthLargest(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]

Algorithm Flow​

Dry Run (Min-Heap)​

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

numheap after pushheap after pop
3[3](size 1, no pop)
2[2,3](size 2, no pop)
1[1,2,3]pop 1 → [2,3]
5[2,3,5]pop 2 → [3,5]
6[3,5,6]pop 3 → [5,6]
4[4,5,6]pop 4 → [5,6]

Return heap[0] = 5 ✓

Complexity​

ApproachTimeSpace
SortO(n log n)O(1)
Min-Heap size kO(n log k)O(k)
QuickSelectO(n) avg, O(n²) worstO(1)

Key Terms​

TermDefinition (in context of this problem)
Min-heap of size kKeeps the k largest elements seen so far; the heap's root (minimum) is always the current k-th largest candidate.
QuickSelectA partition-based selection algorithm (from QuickSort) that recurses into only one side of the pivot, giving O(n) average time.
PartitionRearranges elements around a pivot so everything ≤ pivot comes before it and everything > pivot comes after; the pivot lands at its final sorted index.
Randomized pivotShuffling the array (or picking a random pivot) before QuickSelect avoids the O(n²) worst case on adversarial/sorted input.

FAQ​

  1. Can this be solved without extra space? Yes — QuickSelect sorts in place and uses O(1) extra space (excluding recursion stack), unlike the min-heap approach which needs O(k) space for the heap.
  2. What if k equals the length of the array? Then you're looking for the minimum element; both the heap and QuickSelect approaches handle this correctly since target = len(nums) - k = 0 in QuickSelect, and the heap naturally converges to holding all elements with the smallest at the root.
  3. What if the array has duplicate values? The problem asks for the k-th largest in sorted order (not k-th distinct), so duplicates count individually — both approaches naturally handle this since they operate on value comparisons, not uniqueness.
  4. What's the common follow-up interviewers ask? "Find the k-th largest element in a stream" (LeetCode 703), which requires maintaining a persistent min-heap of size k across add() calls instead of a one-shot computation, or "return the k largest elements" (not just the k-th), which is a direct heap extension.
  5. Why is QuickSelect worst-case O(n²), and how do you mitigate it? If the pivot is always the smallest or largest remaining element (e.g., already-sorted input with a naive last-element pivot), each partition only shrinks the problem by 1, leading to O(n²). Randomizing the pivot (or shuffling the array first) makes this pathological case exponentially unlikely in practice.

Quick Revision​

  • Goal: find the k-th largest element in an unsorted array without necessarily fully sorting it.
  • Min-heap approach: maintain a heap of size k; push each element, pop when size exceeds k; final heap root is the answer. O(n log k) time, O(k) space.
  • QuickSelect approach: partition like QuickSort but recurse only into the side containing the target index (len(nums) - k for k-th largest, 0-indexed from smallest). O(n) average time, O(1) space.
  • Randomize/shuffle before QuickSelect to avoid worst-case O(n²) on adversarial input.
  • Python built-in shortcut: heapq.nlargest(k, nums)[-1], O(n) via an optimized internal heap.
  • Full sort is the simplest baseline: O(n log n) time, O(1) extra space (if in-place sort allowed).
  • QuickSelect mutates the input array via partitioning — flag this if the array must stay unmodified.
  • Classic pitfall: off-by-one on the target index (k-th largest = (n-k)-th smallest in 0-indexed terms).