Kth Largest Element in an Array

Return the k-th largest element in an unsorted array.

Why this is worth learning

Keep the best k values seen so far and expose the weakest retained one. A min-heap makes that threshold available at the root; duplicates occupy separate ranks.

Before coding: one-minute experiment

For [3,2,3,1,2,4,5,5,6] and k=4, why is the answer 4 rather than the fourth distinct value?

Function signature

func FindKthLargest(nums []int, k int) int

Inputs / outputs

• nums: unsorted array.
• k: 1-based rank of the largest element.
• Return: the k-th largest value.

Example

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

Constraints

• 1 <= k <= len(nums) <= 100_000
• The input slice is read-only; duplicate occurrences occupy separate ranks.

Core idea (near-solution)

Sorting a copy gives the answer directly in O(n log n) time. A smaller sufficient summary keeps only the k strongest occurrences. Its weakest entry is the admission threshold: insert a new value, then remove a minimum if there are too many. This is why retaining the largest values uses a min-heap. An in-place quickselect is another algorithm, but this exercise’s input-preservation checks require a copy before partitioning.

Maintain a min-heap with at most k entries. Once k inputs have been read, its root is the kth largest value in the processed prefix; after all inputs it is the answer.

Invariant: after processing i elements and completing any eviction, the heap contains the largest min(k,i) entries with multiplicity.

Algorithm (step-by-step)

1. Initialize an empty min-heap.
2. For each number x in nums:
   • Push x.
   • If heap size > k, pop the smallest.
3. Return the heap top.

Correctness sketch

After each input value, the heap contains the largest min(k,processed) values as a multiset. Inserting the next value temporarily adds one candidate. If the size exceeds k, removing the smallest discards a value no better than any retained one; it can never displace a retained value in the top-k multiset. This preserves the invariant by induction. At the end, the heap contains k largest entries, and its smallest is exactly the kth largest. Sorting the entire input is unnecessary, and equal values are retained according to multiplicity rather than deduplicated.

Trace (hand walkthrough)

Example input:
nums = [3,2,1,5,6,4], k = 2
Output: 5

Walk:
- heap size k=2: push 3 -> [3], push 2 -> [2,3]
- push 1 -> pop 1 -> [2,3]
- push 5 -> pop 2 -> [3,5]
- push 6 -> pop 3 -> [5,6]
- push 4 -> pop 4 -> [5,6] => kth largest = 5

Pitfalls to avoid

• Using a max-heap and popping k-1 times (works but is less efficient).
• Off-by-one errors in k (k is 1-based).

Debugging lens

Check the heap direction: retaining the largest k requires removing the smallest candidate. Test k=1, k=n, duplicates, and negative values. The input is not sorted or mutated by the reference.

Complexity

Time O(n log(k+1)) and auxiliary space O(k). Using log(k+1) makes the linear k=1 case explicit.

Implementation notes (Go)

• Use container/heap with Less based on value for a min-heap.

Reconstruction checkpoint

For [3,2,3,1,2,4,5,5,6] and k=4, why is the answer 4 rather than the fourth distinct value?

Return to Heap / Priority Queue · Module quiz