MediumArrayDivide and ConquerSortingHeap (Priority Queue)Quickselect

Kth Largest Element in an Array

1 approach, code in every language

You are given an integer array `nums` and an integer `k`.

Return the `k`-th largest element in the array. Note that this is the `k`-th largest element in sorted order, not the `k`-th distinct element — duplicate values each count toward the ranking.

Aim to solve it without fully sorting the array.

Example 1

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

Output: 5

Sorted in descending order the array is [6,5,4,3,2,1], so the 2nd largest value is 5.

Example 2

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

Output: 4

Sorted descending it is [6,5,5,4,3,3,2,2,1]; the 4th entry is 4.

Constraints

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

Size-k min-heap

Keep the k largest values seen so far in a min-heap capped at size k; its root is the kth largest.

Loading animation…

Intuition

If we only ever keep the k largest values we have seen, then the smallest of those k is exactly the kth largest overall. A min-heap makes that smallest element cheap to inspect because it always sits at the root. We scan the array, pushing every value into the heap, and whenever the heap grows past size k we pop the current minimum, discarding a value that can never be the answer. After the full scan the heap holds the top k values and its root is the kth largest. A Quickselect partition scheme can also solve this in O(n) average time, but the heap approach is simpler to reason about and streams naturally.

Algorithm walkthrough

1Create an empty min-heap that will hold at most k elements.
2For each value in nums, push it onto the heap.
3If the heap size now exceeds k, pop the root (the current minimum) so only the k largest remain.
4The popped value is too small to be among the top k, so discarding it is safe.
5After processing every element, the heap contains the k largest values.
6Return the root of the heap, which is the smallest of those k and therefore the kth largest.

Implementation

import heapq
from typing import List

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

Time

O(n log k)

Space

O(k)

Each push/pop touches at most log k levels; the heap never holds more than k+1 items. Quickselect achieves O(n) average time but O(n^2) worst case.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Kth Highest Daily Swing is our own problem on the technique behind Kth Largest Element in an Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free