Kth Largest Element in an Array

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given an unsorted array of integers and a number k, return the k-th largest element. This means the k-th largest in sorted order, not the k-th distinct value: in [3, 3, 1], the 2nd largest is 3. Try to do better than sorting the whole array.

    This is the standard question for comparing a heap with quickselect, and for explaining average versus worst-case complexity. Original problem: LeetCode 215.

    Example

    Sorted from largest to smallest, the array is 6, 5, 4, 3, 2, 1, so the 2nd largest is 5.
    Sorted from largest to smallest, the array is 6, 5, 4, 3, 2, 1, so the 2nd largest is 5.
    Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
    Output: 5
    Input:  nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
    Output: 4

    Constraints (assumed)

    • 1 ≤ k ≤ n ≤ 100,000.
    • −10⁴ ≤ value ≤ 10⁴.

    What this question tests

    • Choosing between sorting, a heap and quickselect, and explaining the trade-offs.
    • Getting the heap direction right (a min-heap for the largest values).
    • Understanding average vs. worst case and how randomization helps.

    Questions to ask first

    1. k-th largest counting duplicates, or k-th distinct? (Here: counting duplicates.)
    2. Can I modify the array? Quickselect reorders it in place.
    3. Is k small compared with n? A size-k heap shines when k ≪ n.
    4. Is the data a stream? Then the heap is the natural fit.