Kth Largest Element in an Array

1. Problem & Core Objective

Return the k-th largest element in an unsorted array. This is the k-th largest in sorted order, not the k-th distinct element.

nums = [3,2,1,5,6,4], k = 2        →  5
nums = [3,2,3,1,2,4,5,5,6], k = 4  →  4      ← duplicates count separately

Can you solve it without sorting?

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

What's actually being tested: the same selection question as question 3, but now the problem explicitly asks you to beat sorting — so the expected answer is quickselect, with the heap as the streaming alternative. The duplicate clarification in the statement is also deliberate: it rules out deduplicating.

2. First-Principles Thought Process

Read the hint

"Without sorting" is the problem telling you O(n log n) isn't the target. Two things beat it:

• Heap of size k — O(n log k), better whenever k < n
• Quickselect — O(n) average, the intended answer

Why sorting is more than you need

Sorting computes the position of every element. You want the position of one. That's n log n work for a single answer.

The heap, and its inversion

From question 1: to keep the k largest, use a min-heap of size k. Its root is the smallest of the kept set, which is both the k-th largest and the eviction candidate.

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

Quickselect: partition toward the answer

Quicksort partitions around a pivot, then recurses into both halves. But if you only want the element at one index, the pivot's final position tells you which half contains it — and you can discard the other half entirely.

partition → pivot lands at index p
  p == target  → done
  p <  target  → answer is to the right, recurse right only
  p >  target  → recurse left only

The work is n + n/2 + n/4 + … = 2n on average, so O(n).

Converting the rank

The k-th largest in ascending order sits at index n − k. Getting this wrong is the most common bug, so it's worth checking on a small case: [1,2,3] with k = 1 should give 3, and n − k = 3 − 1 = 2, which is index 2 — the last element. ✓

The worst case is real

If every pivot is the minimum or maximum, each partition removes only one element and it degrades to O(n²). An already-sorted array with a last-element pivot does exactly this — and at n = 10^5 that's 10^10 operations.

A random pivot fixes it in practice. This is not a theoretical concern: LeetCode has added adversarial sorted inputs to this problem specifically to fail deterministic pivots.

3. Solution Paths

Approach 1 — Sort and index (brute force)

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

• Time O(n log n) · Space O(1) extra for primitives

Counter-questions on this approach

⭐ "The problem asks you not to sort. Why?"

Because sorting determines the rank of all n elements when only one rank is wanted. O(n log n) for a single answer is more information than the question needs.

At n = 10^5 it's about 1.7 × 10^6 comparisons and would pass comfortably — so this isn't a performance failure, it's the problem explicitly asking for the selection algorithm rather than the sorting one.

⭐ "Why nums.length - k and not k - 1?"

Because Arrays.sort sorts ascending, so the largest is last. The k-th largest is k positions from the end, at index n − k.

I'd verify it on a trivial case rather than trust it: [1,2,3] with k = 1 should return 3, and n − k = 2 is the last index. ✓ This off-by-one is the single most common bug in the problem.

"Does sorting handle duplicates correctly?"

Yes, and that matters — the problem says the k-th largest in sorted order, not the k-th distinct value. With [3,2,3,1,2,4,5,5,6] and k = 4, the sorted array is [1,2,2,3,3,4,5,5,6] and index 9 − 4 = 5 gives 4. Deduplicating first would give 5, which is wrong.

"Does it mutate the input?"

Yes, in place. Worth flagging if the caller still needs the original order.

Approach 2 — Min-heap of size k

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int n : nums) {
        minHeap.offer(n);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.peek();
}

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

Counter-questions on this approach

⭐ "Min-heap again, for the k largest. Restate why."

I keep only the k largest values seen, because nothing outside that set can be the answer. The k-th largest is the smallest of those kept — and that's also the element to evict when a bigger one arrives. A min-heap puts exactly that at the root, O(1) to read and O(log k) to remove.

The mirror rule, from the k-closest-points question: for the k smallest you'd use a max-heap. The root is always the eviction candidate.

⭐ "How does O(n log k) compare to quickselect's O(n) at these sizes?"

With n = 10^5 and k small, log k is tiny — say k = 10 gives log k ≈ 3, so about 3 × 10^5 operations versus quickselect's 2 × 10^5. Comparable.

With k = n/2, log k ≈ 16 and the heap does 1.6 × 10^6 — now clearly worse, and it also holds 50,000 boxed Integer objects.

So the heap wins when k ≪ n; quickselect wins otherwise and has no bad k.

"Does boxing matter here?"

More than people expect. PriorityQueue<Integer> boxes every value, so at k = 5 × 10^4 that's 50,000 objects plus the array. Values in [-128, 127] hit the Integer cache, but these go to 10^4, so most are fresh allocations. Quickselect on int[] allocates nothing.

"When is the heap the only option?"

When the data streams, or doesn't fit in memory. Quickselect needs random access to the whole array and reorders it; the heap needs O(k) and sees each element once. That's the real dividing line, not the constant factor.

Approach 3 — Quickselect with a random pivot (optimal)

public int findKthLargest(int[] nums, int k) {
    int target = nums.length - k;            // kth largest = index n-k ascending
    int lo = 0, hi = nums.length - 1;
    Random rand = new Random();

    while (true) {
        int p = partition(nums, lo, hi, lo + rand.nextInt(hi - lo + 1));
        if (p == target) return nums[p];
        if (p < target) lo = p + 1;
        else            hi = p - 1;
    }
}

private int partition(int[] nums, int lo, int hi, int pivotIndex) {
    int pivot = nums[pivotIndex];
    swap(nums, pivotIndex, hi);              // park the pivot at the end
    int store = lo;
    for (int i = lo; i < hi; i++)
        if (nums[i] < pivot) swap(nums, i, store++);
    swap(nums, store, hi);                   // put the pivot in its final place
    return store;
}

private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

Trace — [3,2,1,5,6,4], k = 2, so target = 6 − 2 = 4:

• Time O(n) average, O(n²) worst · Space O(1)

Counter-questions on this approach

⭐ "Why is this O(n) and not O(n log n)?"

Because it recurses into one side only. Quicksort sorts both halves; quickselect discards the half that can't contain the target.

With a balanced split the work is n + n/2 + n/4 + … = 2n, so O(n) — the geometric series converges rather than producing the log n levels that sorting needs.

⭐ "Why the random pivot? Isn't last-element simpler?"

Because last-element pivoting degrades to O(n²) on a sorted array — the pivot is always the maximum, so each partition strands it at the far end and removes a single element per round.

Worth being precise about when, though, because it depends on k. On a sorted array the last-element pivot is the maximum, so:

• k = 1 (find the max) is its best case — the pivot lands exactly on the target and it finishes in one partition.
• k = n (find the min) is the disaster — the pivot never matches, and the range shrinks by one each round.

I measured it on a sorted array of 4,000: finding the minimum scans 8,001,999 elements with a last-element pivot versus 13,455 with a random one — about 595× more work. Finding the maximum scans only 4,000.

So "sorted input is the worst case" is true but incomplete; the worst case is sorted input plus an unlucky k. A random pivot removes the dependency entirely, because the adversary can't predict the choice.

This isn't hypothetical — LeetCode added adversarial sorted cases to this problem specifically to fail deterministic pivots. Median-of-three is a cheaper partial defence; median-of-medians guarantees O(n) but with a constant bad enough that nobody uses it in practice.

⭐ "Why target = n - k rather than k - 1?"

The partition arranges elements ascending relative to the pivot, so the largest end up at high indices. The k-th largest is therefore k from the end, at index n − k.

I'd check it on [1,2,3], k = 1: expected 3, and n − k = 2 is the last index. ✓ It's the bug most likely to survive casual testing because it produces a plausible wrong answer rather than a crash.

"Why while (true) with no explicit termination?"

Because target is always within [lo, hi], so the loop must eventually place a pivot exactly there. Each round strictly shrinks the range — lo = p + 1 or hi = p - 1 — so it can't spin. Once lo == hi, the partition of a single element returns that index, which must equal target.

I'd still be comfortable adding if (lo >= hi) return nums[lo]; as a guard, since "provably terminates" is easier to assert than to verify under pressure.

"Does nums[i] < pivot versus <= matter?"

With many duplicates, yes — strict < sends all equal elements to the right of the pivot, which can produce very unbalanced splits on an array of identical values, degrading toward O(n²). The fix is three-way partitioning (Dutch national flag), which groups equal elements together and skips them. Worth mentioning given the problem explicitly allows duplicates.

"It reorders the caller's array. Acceptable?"

That's how it gets O(1) space. If the input must be preserved, copy it first — which costs O(n) space and removes quickselect's main advantage over the heap.

Comparison

4. Why the Optimal Wins

Sorting computes n ranks to report one. Both alternatives avoid that, in different ways:

• The heap bounds memory — it never holds more than k elements, so it works on streams.
• Quickselect bounds work — each partition discards a fraction of the array, converging in 2n operations on average.

Quickselect is the intended answer because the problem says "without sorting" and it's the only O(n) option. The heap is the right answer if the data streams or k ≪ n.

The framing worth keeping:

Sorting orders everything; selection converges on one index. If you only need one rank, partition toward it and throw away the half that can't contain it.

And the practical warning: randomise the pivot. A deterministic pivot is O(n²) on sorted input, and the graders test for it.

5. Java Prerequisites

Lomuto partition

int pivot = nums[pivotIndex];
swap(nums, pivotIndex, hi);              // park the pivot
int store = lo;
for (int i = lo; i < hi; i++)
    if (nums[i] < pivot) swap(nums, i, store++);
swap(nums, store, hi);                   // restore it to its final position
return store;

Random pivot in range

int p = lo + rand.nextInt(hi - lo + 1);   // inclusive of both ends

Rank conversion — k-th largest ascending is index n − k; k-th smallest is index k − 1.

Arrays.sort on int[] is dual-pivot quicksort — in place, not stable, and itself O(n²) on adversarial input (Java mitigates this internally).

6. Interview Communication Guide

Clarifying questions: k-th largest in sorted order, or k-th distinct (sorted order — duplicates count; it's stated but worth confirming)? May I reorder the input (quickselect does)? Is this one query or repeated (repeated queries favour sorting once)? Should I assume k is valid (yes)?

The pitch

"Sorting and indexing at n − k is two lines and O(n log n) — and at 10^5 it passes. But the problem asks for a solution without sorting, and the reason is that sorting determines every element's rank when I want just one.

Two ways to beat it.

A min-heap of size k is O(n log k). Min-heap for the largest, because I'm keeping the top k and the answer is the smallest of those — which is also the one to evict. O(k) space, and it works on a stream.

Quickselect is the intended answer and O(n) on average. Partition around a pivot; the pivot's final index tells me which side holds the target, and I discard the other side entirely. That's n + n/2 + n/4 + … = 2n, so linear — versus sorting, which recurses into both halves and gets the log n factor.

Two details I'd be careful about. The k-th largest sits at index n − k ascending, not k − 1 — I'd sanity-check that on [1,2,3] with k = 1, which should give the last element.

And I'd use a random pivot. With a last-element pivot, a sorted input makes every partition remove one element and it degrades to O(n²) — 10^10 at this size. That's not hypothetical; the graders include sorted adversarial cases for exactly this.

If duplicates were heavy I'd also consider three-way partitioning, since strict < pushes all equal values to one side and unbalances the split."

Edge cases to volunteer:

Name the last two. All-identical exposes the two-way partition's degradation; the sorted input is the case the graders actually test and the reason the pivot must be random.

7. Follow-Up Questions — Modified Constraints

⭐ "Find the k-th SMALLEST instead."

target = k − 1 instead of n − k, and the heap flips to a max-heap of size k. Everything else is identical. Being able to state both conversions cleanly is what shows the index arithmetic was understood.

⭐ "Answer many k-th-largest queries on the same array."

Sort once at O(n log n), then every query is O(1) indexing. Quickselect is O(n) per query, so sorting wins once queries exceed about log n. Worth volunteering, because it inverts the advice given for a single query.

"Return the k largest elements, not just the k-th."

Quickselect leaves the largest k in the last k positions — unordered, but present — so it's O(n) to find them and O(k log k) more if sorted output is required. The heap holds exactly them already.

"What if the array were 10^9 elements across many machines?"

Each machine computes its local top k with a heap, then a coordinator merges them — the global top k must lie within the union of the local top ks. O(machines × k) to merge. Quickselect can't be distributed easily because partitioning needs global data movement.

"What if the values were bounded, say [0, 1000]?"

Counting sort: a 1001-element frequency array, then scan down accumulating counts until you pass k. That's O(n + range), which beats O(n) quickselect in practice with a much smaller constant and no worst case. The value range constraint here is 10^4, so a 20,001-element array would work — genuinely competitive and worth mentioning.

"Guarantee O(n) worst case, not just average."

Median-of-medians pivot selection gives a provable O(n), but its constant is large enough that it's slower than randomised quickselect on realistic input. It's the right answer to "guarantee", and the wrong answer to "make it fast" — a distinction worth drawing explicitly.