Loading…

mediumHeapLC #215Asked very often

Kth Largest Element in an Array

Q: How do you solve Kth Largest Element in an Array using the Sort and Index approach?

When to use it: State first as the obvious baseline, then say 'but the prompt asks if we can do better than sorting'. The most direct route: order the whole array, then read off the element at the kth-largest position. **The index arithmetic.** After sorting **ascending**, the largest element is at index `n−1`, the 2nd largest at `n−2`, and in general the kth largest is at index `n−k`. (Sorting descending instead puts it at `k−1`.) Getting this off-by-one right is the only real trap in this approach — say the formula out loud. **Why it's correct and why it's wasteful.** Sorting trivially places every element in rank order, so indexing is guaranteed right. But we computed the position of *all* n elements to use exactly *one*. The problem's parenthetical 'Can you solve it without sorting?' is a direct hint that the interviewer wants a selection algorithm, not a full sort. **When it's actually the right call.** If you'll answer many queries for different k on the same array, sort once (O(n log n)) and answer each query in O(1) — amortised, sorting wins. Mention this; it shows you weigh the workload, not just the single-query cost. **Why we move on.** For a single query the heap (O(n log k)) and quickselect (O(n) average) both beat O(n log n), and the prompt is fishing for them. Use sort as the baseline you improve upon. Time complexity: O(n log n). Space complexity: O(1) to O(n).

Q: How do you solve Kth Largest Element in an Array using the Min-Heap of Size k approach?

When to use it: The clean, safe interview answer — especially for streaming data or when k ≪ n. Code it confidently. Instead of ranking everything, keep a running collection of the **k largest elements seen so far** in a **min-heap**. **Why a min-heap, and why size k.** The kth largest is, by definition, the *smallest* element among the k largest. A min-heap exposes its smallest element at the root in O(1). So if we maintain exactly the k largest values in a min-heap, the root *is* the answer. We enforce 'exactly k' by pushing each scanned element and, whenever the size exceeds k, popping the root — which evicts the smallest of the current candidates. Anything evicted can't be the kth largest because at least k elements are bigger. **Why min-heap beats the tempting max-heap approach.** A natural first instinct is a max-heap of all n elements, then pop k times. That works but builds a heap of size n (O(n) space) and costs O(n + k log n). The size-k min-heap caps the heap at k, so every operation is O(log k) and space is O(k). When k is small relative to n — the common case — this is dramatically tighter, and it's the version that generalises to *streaming*: you can process an unbounded sequence keeping only k items in memory. **Why the root is the kth largest after the scan.** At the end, the heap contains the k largest values of the whole array (every larger candidate stayed; everything smaller than all k was evicted). Among those k, the root is the minimum — i.e. the k-th from the top. That's precisely the kth largest overall. **Duplicates just work.** Equal values occupy separate heap slots and count toward the rank, matching the 'not distinct' requirement: [3,3,3] with k=2 keeps two 3s and returns 3. Time complexity: O(n log k). Space complexity: O(k).

LCPractice

Heap & Priority Queue · 8 of 9 · 11 min

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

Note that it is the kᵗʰ largest element in the sorted order, not the kᵗʰ distinct element.

Can you solve it without sorting?

In plain English

Return the value that would sit at position k from the largest end if the array were sorted descending. Duplicates count toward the rank — it is not the kth distinct value. k is guaranteed valid (1 ≤ k ≤ n).

Examples

Example 1

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Note: Sorted descending: 6,5,4,3,2,1. The 2nd largest is 5.

Example 2

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Note: Sorted descending: 6,5,5,4,3,2,2,1. Duplicates count, so the 4th element is 4.

Example 3

Input: nums = [1], k = 1
Output: 1
Note: Single element; the 1st largest is itself.

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Clarifying questions4First question: kth largest by value (with duplicates) or kth distinct value?Explore questions

Q1.kth largest by value (with duplicates) or kth distinct value?
By value, duplicates counted. For nums = [3,2,3,1,2,4,5,5,6], k=4 the answer is 4 — the multiset, sorted descending, is 6,5,5,4,... so the 4th is 4.
Q2.Can the array contain negatives?
Yes, -10⁴ ≤ nums[i] ≤ 10⁴. Comparisons handle negatives naturally; no assumptions about sign.
Q3.Is k guaranteed to be within bounds?
Yes, 1 ≤ k ≤ n, so there's always a valid kth largest — no empty-input handling needed.
Q4.Can I mutate the input array?
Worth asking — quickselect reorders nums in place. If the caller needs the original order preserved, copy first or use the heap approach.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the kth largest value (kth in sorted-descending order), not the kth distinct value. The interview-standard answer is a min-heap of size k: scan the array, keep only the k largest seen, and the heap's root is the answer — O(n log k) time, O(k) space. If asked to beat that, quickselect partitions around a random pivot to find the (n−k)th smallest index in O(n) average time, O(1) extra space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you avoid the trivial full-sort, reach for a heap sized to k (not n), and can articulate quickselect's O(n)-average partition idea — plus the index arithmetic kth largest = (n−k)th smallest.

Where candidates slip

Using a max-heap and popping k times (O(n + k log n), heap of size n) when a size-k min-heap is tighter, or botching the quickselect target index / forgetting to randomize the pivot (O(n²) on sorted input).

How to stand out

Offer the spectrum: sort (O(n log n), simplest), size-k min-heap (O(n log k), great for streaming/small k), quickselect (O(n) average, in-place). State the trade-offs and pick based on constraints.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort and Index	`O(n log n)`	`O(1) to O(n)`	State first as the obvious baseline, then say 'but the prompt asks if we can do better than sorting'.	Read
2	Min-Heap of Size k	`O(n log k)`	`O(k)`	The clean, safe interview answer — especially for streaming data or when k ≪ n. Code it confidently.	Read
3	Quickselect — Partition Toward Index n−k (Optimal Average)Optimal	`O(n) average, O(n²) worst`	`O(1)`	When asked to beat O(n log k) or for the theoretically fastest average-case in-place solution.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind kth largestNeed full sorted order too?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Sort and Index

TimeO(n log n)SpaceO(1) to O(n)

State first as the obvious baseline, then say 'but the prompt asks if we can do better than sorting'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the array were sorted, where would the kth largest sit?

2Hint 2Explore hint

Sort ascending; the kth largest is at index n − k. Sort descending; it's at index k − 1.

3Hint 3Explore hint

It works and is one line, but the problem explicitly nudges 'can you do it without sorting?' — flag the wasted work of fully ordering when you need one element.

A · Core idea

The most direct route: order the whole array, then read off the element at the kth-largest position.

The index arithmetic. After sorting ascending, the largest element is at index n−1, the 2nd largest at n−2, and in general the kth largest is at index n−k. (Sorting descending instead puts it at k−1.) Getting this off-by-one right is the only real trap in this approach — say the formula out loud.

Why it's correct and why it's wasteful. Sorting trivially places every element in rank order, so indexing is guaranteed right. But we computed the position of all n elements to use exactly one. The problem's parenthetical 'Can you solve it without sorting?' is a direct hint that the interviewer wants a selection algorithm, not a full sort.

When it's actually the right call. If you'll answer many queries for different k on the same array, sort once (O(n log n)) and answer each query in O(1) — amortised, sorting wins. Mention this; it shows you weigh the workload, not just the single-query cost.

Why we move on. For a single query the heap (O(n log k)) and quickselect (O(n) average) both beat O(n log n), and the prompt is fishing for them. Use sort as the baseline you improve upon.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

sort

ascending

State[1,2,3,4,5,6]

Final result5

C · Code with teaching comments

Reference implementation previewpublic int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }Explore the full code

solution.javaJava

Sort and Index — reference

2 teaching notes

1
public int findKthLargest(int[] nums, int k) {
2
    // Ascending sort; O(n log n) and mutates the input.
3
    Arrays.sort(nums);
4
    // kth largest sits at index n − k after ascending sort.
5
    return nums[nums.length - k];
6
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.6 lines

D · Why it works and complexityO(n log n) timeO(1) to O(n) spaceOpen the invariant and proofExplore the proof

kth largest = element at index n−k after ascending sort. Nailing that index instantly (and noting sort wins for repeated queries) signals you think about the access pattern, not just the asymptotics.

ComplexityO(n log n) time, O(1) to O(n) space — Comparison sort dominates at O(n log n). Space is O(1) for an in-place sort or O(n) for a copy; either way more work than needed since we want a single position.

E · Edge cases and pitfalls5nums = [1], k = 1 — Sorted [1], index n−k = 0 → returns 1.Explore edge cases

Edge cases handled

nums = [1], k = 1Sorted [1], index n−k = 0 → returns 1.
nums = [2,1], k = 2Sorted [1,2], index 0 → returns 1 (the smallest, i.e. 2nd largest).

Pitfalls

Off-by-one: using n − k + 1 or k − 1 on an ascending sort returns the wrong element.
Mutating the caller's array via in-place sort when order must be preserved.
Ignoring the prompt's hint to avoid sorting — leaves performance on the table.

03.2

Approach 2 of 3

Min-Heap of Size k

TimeO(n log k)SpaceO(k)

The clean, safe interview answer — especially for streaming data or when k ≪ n. Code it confidently.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need all elements ranked — only the k largest. What if you maintained just those k as you scan?

2Hint 2Explore hint

Keep a min-heap capped at size k. After pushing each element, if the heap exceeds k, pop the smallest.

3Hint 3Explore hint

After the full scan the heap holds exactly the k largest elements, and its root (the minimum of those) is the kth largest.

A · Core idea

Instead of ranking everything, keep a running collection of the k largest elements seen so far in a min-heap.

Why a min-heap, and why size k. The kth largest is, by definition, the smallest element among the k largest. A min-heap exposes its smallest element at the root in O(1). So if we maintain exactly the k largest values in a min-heap, the root is the answer. We enforce 'exactly k' by pushing each scanned element and, whenever the size exceeds k, popping the root — which evicts the smallest of the current candidates. Anything evicted can't be the kth largest because at least k elements are bigger.

Why min-heap beats the tempting max-heap approach. A natural first instinct is a max-heap of all n elements, then pop k times. That works but builds a heap of size n (O(n) space) and costs O(n + k log n). The size-k min-heap caps the heap at k, so every operation is O(log k) and space is O(k). When k is small relative to n — the common case — this is dramatically tighter, and it's the version that generalises to streaming: you can process an unbounded sequence keeping only k items in memory.

Why the root is the kth largest after the scan. At the end, the heap contains the k largest values of the whole array (every larger candidate stayed; everything smaller than all k was evicted). Among those k, the root is the minimum — i.e. the k-th from the top. That's precisely the kth largest overall.

Duplicates just work. Equal values occupy separate heap slots and count toward the rank, matching the 'not distinct' requirement: [3,3,3] with k=2 keeps two 3s and returns 3.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Size-k min-heap as a sliding 'top-k' filter

push 3

Active call / nodeSupporting contextReturned stateNot active

Each new element pushes in; if the heap overflows k, the smallest is evicted. The root is always the kth largest so far.

Final result5

C · Code with teaching comments

Reference implementation previewpublic int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) {Explore the full code

solution.javaJava

Min-Heap of Size k — reference

4 teaching notes

1
public int findKthLargest(int[] nums, int k) {
2
    // Java's default PriorityQueue is a MIN-heap — exactly what we want here.
3
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
4
    for (int num : nums) {
5
        minHeap.offer(num);
6
        // Cap the heap at k so each op stays O(log k).
7
        if (minHeap.size() > k) {
8
            // Evict the smallest candidate — it can't be among the k largest.
9
            minHeap.poll();
10
        }
11
    }
12
    // Root = smallest of the k largest = the kth largest.
13
    return minHeap.peek();
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n log k) timeO(k) spaceOpen the invariant and proofExplore the proof

The kth largest is the smallest of the k largest — so a min-heap holding exactly the top k puts the answer at its root. Capping the heap at k (evicting the smallest) is what turns O(n log n) into O(n log k) and makes the method stream-friendly.

ComplexityO(n log k) time, O(k) space — Each of n elements triggers a push and possibly a pop on a heap of size ≤ k, each O(log k) → O(n log k). The heap stores at most k elements → O(k) space. When k ≪ n this is much better than O(n log n).

E · Edge cases and pitfalls6nums = [1], k = 1 — Push 1; size 1 not > 1; root = 1.Explore edge cases

Edge cases handled

nums = [1], k = 1Push 1; size 1 not > 1; root = 1.
nums = [3,3,3], k = 2Heap keeps two 3s; root = 3 — duplicates counted correctly.
k == nHeap never overflows; root is the global minimum, which is the nth (smallest) largest.

Pitfalls

Using a max-heap and popping k times — O(n) space and slower when k ≪ n.
Forgetting the size cap, letting the heap grow to n (O(n log n), defeats the purpose).
Returning poll() instead of peek() at the end — poll removes the answer; peek reads it.

03.3

Approach 3 of 3 · Optimal

Quickselect — Partition Toward Index n−k (Optimal Average)

TimeO(n) average, O(n²) worstSpaceO(1)

When asked to beat O(n log k) or for the theoretically fastest average-case in-place solution.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

kth largest is the (n − k)th smallest in 0-indexed sorted order. If you could place just *that* index correctly, you'd be done — no full sort.

2Hint 2Explore hint

Partition around a pivot (Lomuto): everything smaller goes left, larger goes right, and the pivot lands at its final sorted position p.

3Hint 3Explore hint

If p == n − k you're done. If p < n − k recurse on the right side; if p > n − k recurse on the left. Randomize the pivot to avoid O(n²) on sorted input.

A · Core idea

Quickselect is quicksort that only ever recurses into the half containing the answer.

The target index. Sorting ascending, the kth largest lands at index target = n − k. Quickselect's job is to get the element that belongs at target into target — without sorting the rest. We never need the full order, only that one position fixed.

How one partition step makes progress. Pick a pivot and run a Lomuto partition: walk the range, pushing every element strictly smaller than the pivot to the left, then swap the pivot into the boundary store. Now the pivot sits at its final sorted index p: everything left of p is smaller, everything right is ≥. Three cases follow. If p == target, the pivot is the answer — return it. If p < target, the answer is further right, so recurse (or loop) on [p+1, right]. If p > target, recurse on [left, p−1]. Each step discards one side entirely.

Why it's O(n) average but O(n²) worst. Discarding one side means the expected problem size halves each step, so the total work is the geometric series n + n/2 + n/4 + … = 2n = O(n). The disaster case is a pivot that barely shrinks the range — e.g. always picking the largest element on already-sorted input — giving n + (n−1) + … = O(n²). Randomizing the pivot (pick a uniformly random index in [left, right]) destroys any adversarial ordering: the chance of repeatedly bad pivots decays exponentially, so worst case is effectively unreachable in practice. This is the single most important implementation detail — without it, sorted input quietly becomes quadratic.

Why O(1) space and a caveat. Partitioning is in place with a constant number of pointers; using a loop (not recursion) keeps the stack flat too. The trade-off: quickselect mutates the input array's order. If the caller needs the original ordering, copy first — that's the right clarifying question to raise. Duplicates are fine: equal elements distribute around the pivot consistently and the target index still resolves to the correct value.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Quickselect recursion into one side

range [0,5], pivot 4

Active call / nodeSupporting contextReturned stateNot active

Each partition fixes the pivot's index p, then we keep only the side containing target = n − k.

Final result5

C · Code with teaching comments

solution.javaJava

Quickselect — Partition Toward Index n−k (Optimal Average) — optimal

5 teaching notes

1
private final Random rand = new Random();
2
 
3
public int findKthLargest(int[] nums, int k) {
4
    // Map the problem to a single 0-indexed position we must fix.
5
    int target = nums.length - k; // kth largest = (n-k)th smallest
6
    int left = 0, right = nums.length - 1;
7
    while (left < right) {
8
        // Random pivot — the guard against O(n²) on sorted/adversarial input.
9
        int pivotIndex = left + rand.nextInt(right - left + 1);
10
        int p = partition(nums, left, right, pivotIndex);
11
        // Pivot landed exactly at the target index → nums[p] is the answer.
12
        if (p == target) {
13
            return nums[p];
14
        } else if (p < target) {
15
            left = p + 1;
16
        } else {
17
            right = p - 1;
18
        }
19
    }
20
    return nums[left];
21
}
22
 
23
private int partition(int[] nums, int left, int right, int pivotIndex) {
24
    int pivot = nums[pivotIndex];
25
    swap(nums, pivotIndex, right); // park pivot at the end
26
    int store = left;
27
    for (int i = left; i < right; i++) {
28
        if (nums[i] < pivot) {
29
            swap(nums, store, i);
30
            store++;
31
        }
32
    }
33
    // After this, everything left of store < pivot, so store is the pivot's true rank.
34
    swap(nums, store, right); // pivot to its final sorted spot
35
    return store;
36
}
37
 
38
private void swap(int[] nums, int i, int j) {
39
    int tmp = nums[i];
40
    nums[i] = nums[j];
41
    nums[j] = tmp;
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(n) average, O(n²) worst timeO(1) spaceOpen the invariant and proofExplore the proof

Quickselect beats sorting because it throws away half the array each step — it solves a selection problem, not an ordering problem. The whole trick is mapping 'kth largest' to the fixed index n−k and partitioning until a pivot lands exactly there; randomizing the pivot is what keeps the average O(n) honest.

ComplexityO(n) average, O(n²) worst time, O(1) space — Each partition is O(size). Because we recurse into only ONE side, expected work is n + n/2 + n/4 + … = O(n) on average. A pathological pivot sequence (e.g. always the extreme on sorted input) degrades to n + (n−1) + … = O(n²); random pivots make that astronomically unlikely. O(1) extra space (in place).

E · Edge cases and pitfalls7nums = [1], k = 1 — left == right immediately → loop body skipped → return nums[0] = 1.Explore edge cases

Edge cases handled

nums = [1], k = 1left == right immediately → loop body skipped → return nums[0] = 1.
Already sorted [1,2,3,4,5], k = 1Random pivot prevents O(n²); target = 4 resolves to 5. Deterministic last-pivot would degrade here.
All equal [7,7,7,7], any kEvery element equals the pivot; partition puts all in one block, pivot lands consistently, target index returns 7.

Pitfalls

Using a deterministic pivot (first/last element) — O(n²) on sorted input.
Wrong target: kth largest is index n − k, not n − k + 1 or k − 1.
Using `<=` instead of `<` in the partition scan — can mishandle duplicates and infinite-loop the boundary.
Forgetting quickselect mutates the input — clarify whether the caller needs original order.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewprivate final Random rand = new Random(); public int findKthLargest(int[] nums, int k) { int target = nums.length - k; // kth largest = (n-k)th smallest int left = 0, right = nums.length - 1;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

private final Random rand = new Random();

public int findKthLargest(int[] nums, int k) {
    int target = nums.length - k; // kth largest = (n-k)th smallest
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int pivotIndex = left + rand.nextInt(right - left + 1);
        int p = partition(nums, left, right, pivotIndex);
        if (p == target) {
            return nums[p];
        } else if (p < target) {
            left = p + 1;
        } else {
            right = p - 1;
        }
    }
    return nums[left];
}

private int partition(int[] nums, int left, int right, int pivotIndex) {
    int pivot = nums[pivotIndex];
    swap(nums, pivotIndex, right); // park pivot at the end
    int store = left;
    for (int i = left; i < right; i++) {
        if (nums[i] < pivot) {
            swap(nums, store, i);
            store++;
        }
    }
    swap(nums, store, right); // pivot to its final sorted spot
    return store;
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Max-heap of size n instead of min-heap of size k

A max-heap of all n elements popped k times costs O(n + k log n) and O(n) space. A size-k min-heap is O(n log k) and O(k) space — tighter when k ≪ n and stream-friendly.

Explore the code comparison

Don't write this

max_heap = [-x for x in nums]
heapq.heapify(max_heap)        # O(n) space
for _ in range(k - 1):
    heapq.heappop(max_heap)
return -max_heap[0]

Write this instead

min_heap = []
for num in nums:
    heapq.heappush(min_heap, num)
    if len(min_heap) > k:      # cap at k
        heapq.heappop(min_heap)
return min_heap[0]

Wrong quickselect target index

kth largest equals the (n − k)th smallest in 0-indexed order. Using n − k + 1 or k − 1 selects the wrong element.

Explore the code comparison

Don't write this

int target = nums.length - k + 1; // off by one
// ... partition toward target ...

Write this instead

int target = nums.length - k;     // kth largest = (n-k)th smallest

Deterministic pivot on sorted input

Always picking the last element as pivot makes already-sorted arrays shrink the range by 1 each step → O(n²). A random pivot keeps the average at O(n).

Explore the code comparison

Don't write this

pivot_index = right  # last element -- O(n^2) on sorted input

Write this instead

pivot_index = random.randint(left, right)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Min-heap of size k (selection) / Quickselect partition

Code pattern to memorize

min-heap of size k:
    for x in nums:
        push x
        if len(heap) > k: pop_min()   # evict smallest, keep top k
    return heap.peek()                 # kth largest

quickselect: find index n-k in partition order (kth largest = (n-k)th smallest)

Rules to remember

1kth largest = (n−k)th smallest in 0-indexed sorted order — that index is quickselect's target.
2The size-k min-heap keeps the k largest seen; its root is the smallest of the largest = the kth largest.
3Min-heap (not max-heap) for kth largest: you evict the smallest so only big values survive — heap size never exceeds k → O(n log k).
4Randomize the quickselect pivot to dodge the O(n²) worst case on sorted/adversarial input.
5Quickselect recurses into only one side of the partition — that's why it's O(n) average, not O(n log n).
6It's kth largest by value with duplicates counted, not kth distinct — [3,3,3], k=2 is still 3.

Use this pattern when

Need the kth largest/smallest (or top-k) and full sorting is overkill
Streaming data where you keep only the k best seen so far → size-k heap
One-shot selection on an in-memory array and you want O(n) average → quickselect
k is much smaller than n (heap shines: O(n log k) ≪ O(n log n))

Choose another pattern when

Need the array fully sorted afterward → just sort, the kth element falls out
Need kth *distinct* value → dedupe first, then select
Strict worst-case O(n) required → median-of-medians, not random quickselect
Many repeated queries for different k → sort once, answer each in O(1)

Interview takeaway

Selecting the kth largest is the canonical 'don't fully sort' problem. A size-k min-heap gives a clean O(n log k) you can code under pressure; quickselect gives O(n) average by partitioning toward one target index. Knowing both — and when each wins — is exactly what the interviewer is probing.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSelection without full sorting. A size-k min-heap (O(n log k)) holds the top-k with the answer at its root and shines for streams; quickselect (O(n) average) partitions toward index n − k in place. Recognise both whenever you need the kth largest/smallest or top-k. Same family as Top K Frequent Elements, K Closest Points, and Kth Largest in a Stream.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Top K Frequent Elements
Count frequencies, then size-k heap or quickselect/bucket-sort on counts — same selection idea on frequencies.
K Closest Points to Origin
Select k smallest by squared distance — size-k max-heap or quickselect on the distance metric.
Kth Largest Element in a Stream
Coming soon
The streaming version — a persistent size-k min-heap answers each add() in O(log k).
Third Maximum Number
Coming soon
Kth largest with k=3 but DISTINCT values — track top three distinct, watch the dedupe.

Same pattern

←

IPO

Continue · Next problem

Find the Running Median

mediumHeapLC #215Asked very often

Kth Largest Element in an Array

LCPractice

Heap & Priority Queue · 8 of 9 · 11 min

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

Note that it is the kᵗʰ largest element in the sorted order, not the kᵗʰ distinct element.

Can you solve it without sorting?

In plain English

Examples

Example 1

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Note: Sorted descending: 6,5,4,3,2,1. The 2nd largest is 5.

Example 2

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Note: Sorted descending: 6,5,5,4,3,2,2,1. Duplicates count, so the 4th element is 4.

Example 3

Input: nums = [1], k = 1
Output: 1
Note: Single element; the 1st largest is itself.

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Clarifying questions4First question: kth largest by value (with duplicates) or kth distinct value?Explore questions

Q1.kth largest by value (with duplicates) or kth distinct value?
By value, duplicates counted. For nums = [3,2,3,1,2,4,5,5,6], k=4 the answer is 4 — the multiset, sorted descending, is 6,5,5,4,... so the 4th is 4.
Q2.Can the array contain negatives?
Yes, -10⁴ ≤ nums[i] ≤ 10⁴. Comparisons handle negatives naturally; no assumptions about sign.
Q3.Is k guaranteed to be within bounds?
Yes, 1 ≤ k ≤ n, so there's always a valid kth largest — no empty-input handling needed.
Q4.Can I mutate the input array?
Worth asking — quickselect reorders nums in place. If the caller needs the original order preserved, copy first or use the heap approach.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Offer the spectrum: sort (O(n log n), simplest), size-k min-heap (O(n log k), great for streaming/small k), quickselect (O(n) average, in-place). State the trade-offs and pick based on constraints.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort and Index	`O(n log n)`	`O(1) to O(n)`	State first as the obvious baseline, then say 'but the prompt asks if we can do better than sorting'.	Read
2	Min-Heap of Size k	`O(n log k)`	`O(k)`	The clean, safe interview answer — especially for streaming data or when k ≪ n. Code it confidently.	Read
3	Quickselect — Partition Toward Index n−k (Optimal Average)Optimal	`O(n) average, O(n²) worst`	`O(1)`	When asked to beat O(n log k) or for the theoretically fastest average-case in-place solution.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Sort and Index

TimeO(n log n)SpaceO(1) to O(n)

State first as the obvious baseline, then say 'but the prompt asks if we can do better than sorting'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the array were sorted, where would the kth largest sit?

2Hint 2Explore hint

Sort ascending; the kth largest is at index n − k. Sort descending; it's at index k − 1.

3Hint 3Explore hint

It works and is one line, but the problem explicitly nudges 'can you do it without sorting?' — flag the wasted work of fully ordering when you need one element.

A · Core idea

The most direct route: order the whole array, then read off the element at the kth-largest position.

Why we move on. For a single query the heap (O(n log k)) and quickselect (O(n) average) both beat O(n log n), and the prompt is fishing for them. Use sort as the baseline you improve upon.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

sort

ascending

State[1,2,3,4,5,6]

Final result5

C · Code with teaching comments

Reference implementation previewpublic int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }Explore the full code

solution.javaJava

Sort and Index — reference

2 teaching notes

1
public int findKthLargest(int[] nums, int k) {
2
    // Ascending sort; O(n log n) and mutates the input.
3
    Arrays.sort(nums);
4
    // kth largest sits at index n − k after ascending sort.
5
    return nums[nums.length - k];
6
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.6 lines

D · Why it works and complexityO(n log n) timeO(1) to O(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5nums = [1], k = 1 — Sorted [1], index n−k = 0 → returns 1.Explore edge cases

Edge cases handled

nums = [1], k = 1Sorted [1], index n−k = 0 → returns 1.
nums = [2,1], k = 2Sorted [1,2], index 0 → returns 1 (the smallest, i.e. 2nd largest).

Pitfalls

Off-by-one: using n − k + 1 or k − 1 on an ascending sort returns the wrong element.
Mutating the caller's array via in-place sort when order must be preserved.
Ignoring the prompt's hint to avoid sorting — leaves performance on the table.

03.2

Approach 2 of 3

Min-Heap of Size k

TimeO(n log k)SpaceO(k)

The clean, safe interview answer — especially for streaming data or when k ≪ n. Code it confidently.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need all elements ranked — only the k largest. What if you maintained just those k as you scan?

2Hint 2Explore hint

Keep a min-heap capped at size k. After pushing each element, if the heap exceeds k, pop the smallest.

3Hint 3Explore hint

After the full scan the heap holds exactly the k largest elements, and its root (the minimum of those) is the kth largest.

A · Core idea

Instead of ranking everything, keep a running collection of the k largest elements seen so far in a min-heap.

Duplicates just work. Equal values occupy separate heap slots and count toward the rank, matching the 'not distinct' requirement: [3,3,3] with k=2 keeps two 3s and returns 3.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Size-k min-heap as a sliding 'top-k' filter

push 3

Active call / nodeSupporting contextReturned stateNot active

Each new element pushes in; if the heap overflows k, the smallest is evicted. The root is always the kth largest so far.

Final result5

C · Code with teaching comments

solution.javaJava

Min-Heap of Size k — reference

4 teaching notes

1
public int findKthLargest(int[] nums, int k) {
2
    // Java's default PriorityQueue is a MIN-heap — exactly what we want here.
3
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
4
    for (int num : nums) {
5
        minHeap.offer(num);
6
        // Cap the heap at k so each op stays O(log k).
7
        if (minHeap.size() > k) {
8
            // Evict the smallest candidate — it can't be among the k largest.
9
            minHeap.poll();
10
        }
11
    }
12
    // Root = smallest of the k largest = the kth largest.
13
    return minHeap.peek();
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n log k) timeO(k) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6nums = [1], k = 1 — Push 1; size 1 not > 1; root = 1.Explore edge cases

Edge cases handled

nums = [1], k = 1Push 1; size 1 not > 1; root = 1.
nums = [3,3,3], k = 2Heap keeps two 3s; root = 3 — duplicates counted correctly.
k == nHeap never overflows; root is the global minimum, which is the nth (smallest) largest.

Pitfalls

Using a max-heap and popping k times — O(n) space and slower when k ≪ n.
Forgetting the size cap, letting the heap grow to n (O(n log n), defeats the purpose).
Returning poll() instead of peek() at the end — poll removes the answer; peek reads it.

03.3

Approach 3 of 3 · Optimal

Quickselect — Partition Toward Index n−k (Optimal Average)

TimeO(n) average, O(n²) worstSpaceO(1)

When asked to beat O(n log k) or for the theoretically fastest average-case in-place solution.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

kth largest is the (n − k)th smallest in 0-indexed sorted order. If you could place just *that* index correctly, you'd be done — no full sort.

2Hint 2Explore hint

Partition around a pivot (Lomuto): everything smaller goes left, larger goes right, and the pivot lands at its final sorted position p.

3Hint 3Explore hint

If p == n − k you're done. If p < n − k recurse on the right side; if p > n − k recurse on the left. Randomize the pivot to avoid O(n²) on sorted input.

A · Core idea

Quickselect is quicksort that only ever recurses into the half containing the answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Quickselect recursion into one side

range [0,5], pivot 4

Active call / nodeSupporting contextReturned stateNot active

Each partition fixes the pivot's index p, then we keep only the side containing target = n − k.

Final result5

C · Code with teaching comments

solution.javaJava

Quickselect — Partition Toward Index n−k (Optimal Average) — optimal

5 teaching notes

1
private final Random rand = new Random();
2
 
3
public int findKthLargest(int[] nums, int k) {
4
    // Map the problem to a single 0-indexed position we must fix.
5
    int target = nums.length - k; // kth largest = (n-k)th smallest
6
    int left = 0, right = nums.length - 1;
7
    while (left < right) {
8
        // Random pivot — the guard against O(n²) on sorted/adversarial input.
9
        int pivotIndex = left + rand.nextInt(right - left + 1);
10
        int p = partition(nums, left, right, pivotIndex);
11
        // Pivot landed exactly at the target index → nums[p] is the answer.
12
        if (p == target) {
13
            return nums[p];
14
        } else if (p < target) {
15
            left = p + 1;
16
        } else {
17
            right = p - 1;
18
        }
19
    }
20
    return nums[left];
21
}
22
 
23
private int partition(int[] nums, int left, int right, int pivotIndex) {
24
    int pivot = nums[pivotIndex];
25
    swap(nums, pivotIndex, right); // park pivot at the end
26
    int store = left;
27
    for (int i = left; i < right; i++) {
28
        if (nums[i] < pivot) {
29
            swap(nums, store, i);
30
            store++;
31
        }
32
    }
33
    // After this, everything left of store < pivot, so store is the pivot's true rank.
34
    swap(nums, store, right); // pivot to its final sorted spot
35
    return store;
36
}
37
 
38
private void swap(int[] nums, int i, int j) {
39
    int tmp = nums[i];
40
    nums[i] = nums[j];
41
    nums[j] = tmp;
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(n) average, O(n²) worst timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7nums = [1], k = 1 — left == right immediately → loop body skipped → return nums[0] = 1.Explore edge cases

Edge cases handled

nums = [1], k = 1left == right immediately → loop body skipped → return nums[0] = 1.
Already sorted [1,2,3,4,5], k = 1Random pivot prevents O(n²); target = 4 resolves to 5. Deterministic last-pivot would degrade here.
All equal [7,7,7,7], any kEvery element equals the pivot; partition puts all in one block, pivot lands consistently, target index returns 7.

Pitfalls

Using a deterministic pivot (first/last element) — O(n²) on sorted input.
Wrong target: kth largest is index n − k, not n − k + 1 or k − 1.
Using `<=` instead of `<` in the partition scan — can mishandle duplicates and infinite-loop the boundary.
Forgetting quickselect mutates the input — clarify whether the caller needs original order.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

private final Random rand = new Random();

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Max-heap of size n instead of min-heap of size k

A max-heap of all n elements popped k times costs O(n + k log n) and O(n) space. A size-k min-heap is O(n log k) and O(k) space — tighter when k ≪ n and stream-friendly.

Explore the code comparison

Don't write this

max_heap = [-x for x in nums]
heapq.heapify(max_heap)        # O(n) space
for _ in range(k - 1):
    heapq.heappop(max_heap)
return -max_heap[0]

Write this instead

min_heap = []
for num in nums:
    heapq.heappush(min_heap, num)
    if len(min_heap) > k:      # cap at k
        heapq.heappop(min_heap)
return min_heap[0]

Wrong quickselect target index

kth largest equals the (n − k)th smallest in 0-indexed order. Using n − k + 1 or k − 1 selects the wrong element.

Explore the code comparison

Don't write this

int target = nums.length - k + 1; // off by one
// ... partition toward target ...

Write this instead

int target = nums.length - k;     // kth largest = (n-k)th smallest

Deterministic pivot on sorted input

Always picking the last element as pivot makes already-sorted arrays shrink the range by 1 each step → O(n²). A random pivot keeps the average at O(n).

Explore the code comparison

Don't write this

pivot_index = right  # last element -- O(n^2) on sorted input

Write this instead

pivot_index = random.randint(left, right)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Min-heap of size k (selection) / Quickselect partition

Code pattern to memorize

min-heap of size k:
    for x in nums:
        push x
        if len(heap) > k: pop_min()   # evict smallest, keep top k
    return heap.peek()                 # kth largest

quickselect: find index n-k in partition order (kth largest = (n-k)th smallest)

Rules to remember

1kth largest = (n−k)th smallest in 0-indexed sorted order — that index is quickselect's target.
2The size-k min-heap keeps the k largest seen; its root is the smallest of the largest = the kth largest.
3Min-heap (not max-heap) for kth largest: you evict the smallest so only big values survive — heap size never exceeds k → O(n log k).
4Randomize the quickselect pivot to dodge the O(n²) worst case on sorted/adversarial input.
5Quickselect recurses into only one side of the partition — that's why it's O(n) average, not O(n log n).
6It's kth largest by value with duplicates counted, not kth distinct — [3,3,3], k=2 is still 3.

Use this pattern when

Need the kth largest/smallest (or top-k) and full sorting is overkill
Streaming data where you keep only the k best seen so far → size-k heap
One-shot selection on an in-memory array and you want O(n) average → quickselect
k is much smaller than n (heap shines: O(n log k) ≪ O(n log n))

Choose another pattern when

Need the array fully sorted afterward → just sort, the kth element falls out
Need kth *distinct* value → dedupe first, then select
Strict worst-case O(n) required → median-of-medians, not random quickselect
Many repeated queries for different k → sort once, answer each in O(1)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Top K Frequent Elements
Count frequencies, then size-k heap or quickselect/bucket-sort on counts — same selection idea on frequencies.
K Closest Points to Origin
Select k smallest by squared distance — size-k max-heap or quickselect on the distance metric.
Kth Largest Element in a Stream
Coming soon
The streaming version — a persistent size-k min-heap answers each add() in O(log k).
Third Maximum Number
Coming soon
Kth largest with k=3 but DISTINCT values — track top three distinct, watch the dedupe.

Same pattern

←

IPO

Continue · Next problem

Find the Running Median