Kth Largest Element in an Array – Solution & Complexity

• Sort nums from largest to smallest and return the value at position k (1-based).
• For [3,2,1,5,6,4] the descending order is 6, 5, 4, 3, 2, 1, so with k = 2 the answer is 5.
• The simplest correct solution is exactly that: sort and index. It costs O(n log n) time, but it orders all n values when we only care about the top k.

• Scan the array once and keep a small set of candidates: the k largest values seen so far.
• When a new value arrives, it joins the candidates. If that makes k + 1 candidates, the smallest one can never be the answer any more — at least k values are already larger than or equal to it — so drop it.
• After the last value, the candidates are exactly the k largest values in the array, and the smallest candidate is the kth largest.
• So we need a structure that cheaply answers "what is the smallest candidate?" and removes it. That is a min-heap of size at most k.

• Invariant: after processing each value, the heap holds the k largest values seen so far (or all of them, if fewer than k have been seen).
• A min-heap keeps its smallest element at the root, so the candidate to evict is always heap[0]. Push and pop each cost O(log k) because the heap never grows past k + 1 elements.
• At the end the root is the smallest of the k largest values, i.e. the kth largest. Read it without popping.
• A max-heap would put the largest value on top, which is the wrong value to evict. You could instead heapify all n values into a max-heap and pop k - 1 times, but that keeps O(n) values in memory instead of O(k).

Each step pushes the value, then pops the root if the heap holds more than k = 2 values. The candidates column lists the retained values sorted for readability; it is not the heap's internal array layout.

The final candidates {5, 6} are the two largest values, and the root 5 is the answer.

• Equal values occupy separate positions. For nums = [3,2,3,1,2,4,5,5,6] the descending order is 6, 5, 5, 4, 3, 3, 2, 2, 1.
• With k = 4 the answer is 4. If you deduplicated first, the distinct values 6, 5, 4, 3 would give 3 — a different (wrong) answer.
• The heap handles this naturally: both 5s are pushed as separate entries, and the final candidates are {4, 5, 5, 6} with root 4. Do not use a set for the candidates.
• Other edge cases: k = 1 returns the maximum, k = n returns the minimum, negative values and all-equal arrays (e.g. [5,5,5], k = 2 → 5) need no special handling.