LeetEye LeetEye
Hard Heap / Priority Queue ~5 min

Kth Largest Element in an Array

heap kth-largest-element-in-an-array

Problem

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

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Examples

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
Key Insight

Min-heap of size k: process all elements, keeping k largest. Root is kth largest.

Min-heap of size k: process all elements, keeping k largest. Root is kth largest. Quickselect for O(n) average.

How to Approach This Problem

Pattern Recognition: When you see keywords like kth largest element in an array heap, think Heap / Priority Queue.

Step-by-Step Reasoning

1 Sort descending, return arr[k-1]:
Answer: Works, O(n log n)
Sorting works but isn't optimal. O(n log n) time.
2 Min-heap of size k gives kth largest because:
Answer: Both A and C
Heap keeps k largest. Min among them = kth largest overall.
3 Using heap of size n vs size k:
Answer: Size k is faster for k << n
O(n log k) vs O(n log n). When k is small, log k << log n.
4 Quickselect is like quicksort but:
Answer: Only recurses on one side
We only care about kth position. Recurse only on the side containing it.
5 After partition around pivot, if pivot is at index p:
Answer: All of the above
Partition puts pivot in correct sorted position. Compare with target position n-k.
6 For guaranteed O(n log k) with simple code:
Answer: Heap
Quickselect is O(n) average but O(n^2) worst. Heap is reliably O(n log k).

Solution

import heapq

def findKthLargest(nums: List[int], k: int) -> int:
    # Min-heap of size k
    heap = []
    
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    
    return heap[0]

Complexity Analysis

Time O(n log k)
Space O(k)

Master This Pattern

Build intuition with interactive MCQs. Practice Heap / Priority Queue problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye