Kth Largest Element in an Array

Learning goal: Translate the kth-largest question into a streaming selection problem.

Core idea We need the value that ranks kth from the top, not the complete sorted order. For the example nums = [3,2,1,5,6,4] and k = 2, the answer is 5 because only 6 is larger. A useful algorithm should discard values that cannot affect the final top k.

Algorithm plan

• Read the numbers from left to right.
• Keep a compact structure representing the strongest candidates so far.
• Remove the weakest candidate whenever too many candidates are stored.
• Read the final boundary value as the answer.

Micro-example After seeing [3,2,1] with k = 2, the two largest values are 3 and 2. The next value, 5, replaces 2, because 2 is no longer among the two largest seen values.

Pitfalls

• Do not confuse kth largest with index k - 1 in the original array.
• Duplicates still occupy ranking positions.
• The algorithm should not accidentally retain more than k candidates.

Recap

• We need a rank, not a fully sorted array.
• Maintain only the best k candidates.
• The weakest member of that group determines the kth-largest value.

Learning goal: Understand why a min-heap of size k stores exactly the k largest values seen so far.

Core idea A min-heap exposes its smallest element at the root. Store each incoming number in the heap, then remove the root whenever the heap grows beyond size k. The removed value is the weakest candidate, so after trimming, the heap contains the k largest values encountered so far.

Data structure model

Micro-example With k = 2, after processing 3, 2, the heap contains [2,3]. After pushing 5, pop 2; the heap becomes [3,5], the two largest values so far.

Pitfalls

• A max-heap keeps the largest value visible, but does not efficiently remove the weakest top-k candidate.
• Trim immediately after each push, rather than waiting until the end.
• The heap's internal array is not fully sorted.

Recap

• A min-heap makes the weakest top-k candidate easy to remove.
• Its root is the kth-largest value after all numbers are processed.
• The heap never needs more than k retained values.

Learning goal: Turn the invariant into an implementation with the target complexity.

Core idea Each number gets one heap insertion. If that insertion creates k + 1 elements, the minimum cannot remain in the top k, so removing it restores the invariant. By induction, the heap represents the top k values after every processed prefix.

Algorithm plan

• Create an empty min-heap.
• For each value in nums, push value.
• If the heap size is greater than k, pop once.
• Return the minimum at the root after the scan.

heap = []
for value in nums:
    heappush(heap, value)
    if len(heap) > k:
        heappop(heap)
return heap[0]

Micro-example For [3,2,1,5,6,4], k = 2, the final heap contains [5,6]. Its root is 5, so the second-largest value is 5.

Pitfalls

• The heap API must be a min-heap; some languages provide only a max-heap by default.
• Do not return the last inserted value.
• If k = nums.length, no element is popped and the root is the minimum array value.

Recap

• Push every value and trim when size exceeds k.
• The invariant proves the retained set is top-k.
• Time is O(n log k) and auxiliary space is O(k).

Learning goal: Trace how each push and pop transforms the heap on a complete example.

Core idea Use nums = [3,2,1,5,6,4] and k = 2. The heap is allowed to retain only two values. Whenever a third value arrives, the minimum is removed because it cannot belong to the top two seen so far.

Algorithm plan

• Push 3, then 2; the heap has room for two values.
• Push 1; remove 1, leaving [2,3].
• Push 5; remove 2, leaving [3,5].
• Push 6; remove 3, leaving [5,6].
• Push 4; remove 4, leaving [5,6].
• Return the root, 5.

Micro-example The final retained set is {5,6}. It is not important that the heap's internal array is [5,6] in sorted order; the important fact is that its root is the smallest member of the top-two set.

Pitfalls

• Do not interpret a pop as removing the globally largest value; it removes the smallest retained candidate.
• A heap display is a structural representation, not necessarily a sorted list.
• Keep the same k throughout the pass.

Recap

• Every overflow causes exactly one removal.
• The heap ends as [5,6] for this example.
• The root gives the requested answer: 5.

Learning goal: Recognize when the heap method is correct and when a different choice may be preferable.

Core idea The most common mistake is sorting the entire array even though only one rank is needed. Sorting establishes every pairwise order, while the heap preserves only the k strongest values. The heap method is especially effective when k is small or values arrive as a stream.

Algorithm plan

• Check that k is within the array length.
• Use a min-heap and trim after every insertion.
• Treat equal values as separate elements.
• Consider quickselect when average linear time and in-place partitioning are priorities.

Micro-example For [5,5,4] and k = 2, the answer is 5; the two equal values occupy the first and second ranks. For k = nums.length, the heap keeps every value, so its root is the minimum.

Pitfalls

• Forgetting duplicates changes the rank calculation.
• Returning the maximum from a min-heap gives the wrong boundary.
• Claiming quickselect is always O(n) ignores its possible worst case.

Recap

• Sorting is valid but often unnecessarily expensive.
• Heap trimming handles duplicates and edge values naturally.
• Quickselect is an average O(n) alternative with different trade-offs.

Learning goal: Compare the heap solution with quickselect and choose the right tool.

Core idea A heap operation costs O(log k) because the heap contains at most k elements. Performing one push for each of n values gives O(n log k) time, while the heap storage is O(k). Quickselect partitions around pivots and has average O(n) time, but its worst case can be O(n^2).

Algorithm plan

• Use the heap when predictable performance, streaming input, or simple correctness matters.
• Use quickselect when average linear time and in-place selection are important.
• Use full sorting only when the sorted order will be reused or simplicity outweighs the extra work.

Micro-example If k is much smaller than n, log k is much smaller than log n, so the heap avoids maintaining irrelevant low values. If k is close to n, the heap's advantage over sorting becomes less pronounced.

Pitfalls

• Space O(k) refers to auxiliary heap storage, not the input array.
• Quickselect's O(n) is an average-case claim.
• Complexity should reflect the operation actually used, not a different alternative.

Recap

• Heap: O(n log k) time and O(k) space.
• Quickselect: average O(n) time and typically O(1) extra space.
• The final heap root is the kth-largest answer.