K-th Largest Element in an Array

Given an integer array arr and an integer k, return the k-th largest element (with k = 1 meaning the maximum). Note this is the k-th largest in sorted order, not the k-th distinct value. If k is out of range (k < 1 or k > the array length), return -1.

Hints

· Stuck? Reveal one nudge at a time.

You don't need the whole sorted order — only the boundary between the top k and the rest.

Keep a min-heap holding the k largest elements seen so far.

When the heap exceeds size k, pop the smallest; the root is the k-th largest.

Common doubts

A size-k min-heap keeps the k largest and exposes their smallest (the k-th largest) at the root in O(1). A max-heap of everything would cost O(n) space and O(n log n).

When k is much smaller than n: O(n log k) vs O(n log n). For k close to n, sorting is comparable and simpler.

No — duplicates count as separate elements, matching sorted-order position k.

Interview follow-ups

· What an interviewer asks next.

The size-k min-heap works unchanged — that's the k-th-largest-in-a-stream problem.

Yes — Quickselect partitions around a pivot to place the k-th element in expected linear time.

Fun facts

This is LeetCode 215, one of the most-asked heap questions in interviews.
The size-k min-heap is the seed pattern for 'k closest', 'top-k frequent', and 'merge k lists'.

Asked at

AmazonFacebookMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: arr = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Sorted descending is [6, 5, 4, 3, 2, 1]; the 2nd largest is 5.

Example 2

Input: arr = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Duplicates count: the 4th largest by value is 4.

Constraints

- 0 <= arr.length <= 10^5 - -10^9 <= arr[i] <= 10^9 - 1 <= k <= 10^5

The one-liner is to sort the array descending and take index k-1 — correct, O(n log n). The interview-favourite improvement uses a size-k min-heap: it finds the k-th largest without fully sorting, and it's the template for streaming and top-k problems.

Why a min-heap of size k? Keep the k largest elements seen so far in a min-heap. For each value, push it; if the heap exceeds k, pop the smallest. The heap always holds the current top-k, and its root — the smallest of those k — is exactly the k-th largest overall. Each push/pop is O(log k), so the pass is O(n log k) time and O(k) space — better than sorting when k is small relative to n.

Prerequisites

Before you start

· Concepts used directly in the solution.

Min-heap. a priority queue exposing the smallest element in O(1).

Top-k invariant. a size-k min-heap holds the k largest; its root is the k-th largest.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“k-th largest by value or by distinct value?”

By value in sorted order — duplicates count.

“What if k exceeds the array length?”

Return -1.

The ideal opening — say it like this

I keep a size-k min-heap of the largest elements seen; when it overflows I pop the smallest.

The heap's root is the k-th largest, found in O(n log k) time and O(k) space.

Understand the problem

Worked example — arr = [3, 2, 1, 5, 6, 4], k = 2

push 3        -> [3]
push 2        -> [2,3]           (size 2)
push 1 pop    -> [2,3]           (1 < root 2, evicted)
push 5 pop    -> [3,5]           (2 evicted)
push 6 pop    -> [5,6]           (3 evicted)
push 4 pop    -> [5,6]           (4 evicted)
root = 5 -> the 2nd largest

Key observations

1Aha

Only the top-k boundary matters

The k-th largest is the smallest of the k largest — no full sort needed.

2Aha

A size-k min-heap tracks that boundary

Push each element, pop the smallest whenever the heap exceeds k.

3Aha

O(n log k) time, O(k) space

Cheaper than sorting when k ≪ n.

Brute force vs optimal

	Sort	Size-k min-heap
Idea	Sort descending, take index k-1	Keep the k largest; root is the answer
Time	O(n log n)	O(n log k)
Space	O(n) or O(1) in place	O(k)

The heap wins for small k and extends to streams, where sorting can't. Full code is in the Approaches selector below.

Summary

Key takeaway

Keep a size-k min-heap of the largest elements; its root is the k-th largest. O(n log k) time, O(k) space — no full sort needed.

for x in arr:
    push x
    if size > k: pop the smallest
return heap root