How do you approach Kth Largest Element in an Array?

You can use a min-heap of size k.

What is the time complexity of Kth Largest Element in an Array?

Time complexity: O(n) average for Quickselect, O(n log k) for heap. Space complexity: O(k) for heap, O(1) for Quickselect.

What are common mistakes on Kth Largest Element in an Array?

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k). An inverted comparator, which is silent: the code runs and returns confidently wrong answers. Re-heapifying inside the loop instead of once up front.

gitGood.dev

← Back to problems

Kth Largest Element in an Array

MediumAlgorithms

Description

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 the 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

Constraints

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

Kth Largest Element in an Array: approach, complexity and pitfalls

A medium heap / priority queue problem, graded against 6 test cases (3 of them hidden).

The pattern: Heap / Priority Queue

A priority queue for "top k" and streaming-median questions.

Reach for it when you see: "Top/smallest k", a running median, or repeatedly needing the current minimum.

More Heap / Priority Queueproblems →

If you are stuck

Show the 3-step hint ladder

You can use a min-heap of size k.
Or use the Quickselect algorithm (similar to quicksort).
For heap: keep k largest elements, return the smallest among them.

The optimal approach

Show the approach: Solution 1: Min-Heap

Maintain a min-heap of size k. The root is the kth largest.

Solution 2: Quickselect

Partition around a pivot until we find the kth largest position.

Time: O(n) average for Quickselect, O(n log k) for heap
Space: O(k) for heap, O(1) for Quickselect

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Heap / Priority Queue mistakes

These apply to the pattern as a whole, not just this problem.

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k).
An inverted comparator, which is silent: the code runs and returns confidently wrong answers.
Re-heapifying inside the loop instead of once up front.