• 1 <= k <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• The array is not sorted and may contain duplicates and negative numbers.
• Follow-up: can you avoid sorting the whole array? Can you reach O(N) average time?

Read the question slowly, because one word does the work: position. You are not asked for the biggest value, or for any value above some threshold. You are asked for whatever value happens to land in slot k when everything is lined up from biggest to smallest. That is an ordering question with a very narrow output — one number out of N.

Sort the array from biggest to smallest, then read index k-1.

def find_kth_largest(nums, k):
    nums.sort(reverse=True)   # biggest first
    return nums[k - 1]        # slot k, zero-indexed

This is correct, and if an interviewer stops you here you have already solved it. But look at what it bought. Sorting settles the relative order of every pair of elements: it decides whether the 900th largest beats the 901st, whether the last two elements are the right way round, everything. That is roughly N log N units of work — for N = 100,000 that is around 1.7 million comparisons. We then throw all of it away except a single lookup.

Name the waste precisely: we computed a total order when the question only depends on one boundary. Everything below slot k is irrelevant, and the ordering within the top k is irrelevant too. We only need to know which k elements are the biggest, and which of those k is the weakest.

Here is the change in point of view. Walk the array once, and maintain a shortlist of the best k numbers seen so far — nothing else. When a new number arrives there are only two possibilities:

Notice what this needs. It never asks "what is the biggest number so far" and never asks for the shortlist in order. It asks one question over and over: what is the smallest thing on my shortlist, and can I remove it cheaply? Once the whole array has passed through, the shortlist holds exactly the k largest values, and the weakest survivor — the smallest of the top k — is the kth largest. That is the answer, sitting at the door.

So the question becomes purely mechanical: which data structure answers "give me the current minimum, and let me delete it" fast, while also letting me insert fast?

A plain list can find its minimum, but only by scanning all k entries — that puts us back to slow. Keeping the list sorted makes the minimum free to read, but every insertion has to shift elements to make room, which is again linear. We want something in between: not fully sorted, just sorted enough that the extreme is always on top.

A heap is exactly that. Picture a binary tree where every parent holds a value smaller than or equal to both of its children. That single rule — called the heap property — says nothing about siblings; the left child and the right child may be in any order relative to each other. But applied all the way down, it forces the global minimum to the root, because the root is smaller than its children, which are smaller than theirs, and so on. This is a min-heap. Flip the comparison and every parent is larger than its children: a max-heap, with the maximum on top.

The tree is not built from node objects. It is stored in a flat array, where the children of index i live at 2i+1 and 2i+2, and the tree is kept "complete" — every level filled left to right with no gaps — so the array has no holes.

Why are operations cheap? To insert, append the new value at the end of the array and repeatedly swap it upward while it is smaller than its parent. To delete the root, move the last element into the root slot and repeatedly swap it downward with its smaller child until the property holds again. In both cases the value travels one level per swap, and a complete binary tree over k elements has about log₂ k levels. Ten thousand elements is about 14 levels. That is what "O(log k)" means here: the cost is the depth, not the size.

Reading the top is free, O(1), because it is just index 0.

import heapq   # Python's heapq is a MIN-heap

def find_kth_largest(nums, k):
    shortlist = []
    for num in nums:
        heapq.heappush(shortlist, num)      # O(log k)
        if len(shortlist) > k:
            heapq.heappop(shortlist)        # drop the weakest survivor
    return shortlist[0]                     # smallest of the top k

Pushing then popping when the size exceeds k is deliberately written that way rather than as a compare-first version. It keeps the size invariant obvious — after every iteration the shortlist holds at most k items — and it removes an edge case: while fewer than k numbers have been seen, everything is simply accepted, with no separate "still filling up" branch to get wrong.

Each of the N numbers costs at most one push and one pop, each O(log k). Total: O(N log k) time and O(k) memory. When k is small this is dramatically better than sorting — for N = 100,000 and k = 5, log k is about 2 instead of 17.

Negatives included on purpose — nothing about the mechanism cares about sign.

Return the root: 3. Check by hand: sorted biggest-first the array reads 5, 4, 3, 2, -1, -1, and the 3rd slot is indeed 3.

Strip away the specifics and a reusable shape remains. A bounded heap solves "the top k by some measure" in one pass, and adapting it to a new problem is filling three slots:

The precondition is milder than for most patterns: the elements only need to be comparable by the key. There is no requirement that the input be sorted or positive. The invariant that makes it correct is worth stating exactly, because it is what you argue in an interview: after processing any prefix of the array, the heap contains precisely the k largest elements of that prefix. It holds at the start trivially, and each step preserves it, since the only element ever discarded is one provably outside the top k of the enlarged prefix.

Recognition signals in an unseen statement: the words "k largest / k smallest / k closest / k most frequent" with k much smaller than N; a stream where the data does not fit in memory and cannot be sorted at all; a constraint like N up to 10⁵ combined with repeated queries, which rules out re-sorting each time. All three are the same underlying situation — you need a partial order, and sorting overpays for it.

Where it stops being the best tool: if you need the full ranking, sort — a heap gives you no discount. If the keys are small bounded integers, counting them into buckets beats any comparison-based method outright, which is exactly the twist waiting in Top K Frequent. And if you need only one position with no stream and no memory limit, Quickselect is faster still.

Since the follow-up asks for linear average time, here is the idea. Pick a pivot value and partition the array so that everything larger than the pivot ends up on the left and everything smaller on the right. After partitioning, the pivot is sitting in its final sorted position — nothing else about the array is ordered, but that one index is settled. If that index is k-1, the pivot is the answer. If it is greater than k-1, the answer lies to the left, so recurse there and ignore the right side entirely; otherwise recurse right.

The cost analysis is what makes it worth knowing. Each partition pass is linear in the region you scan, and a random pivot splits the region roughly in half, so the work is about N + N/2 + N/4 + …, a series that sums to about 2N. That is O(N) on average. The catch: with an unlucky pivot the split can be maximally lopsided every time — one element on one side — degrading to O(N²). Choosing the pivot at random is what makes that adversarially impossible rather than merely unlikely.

The honest trade: Quickselect is faster on average but has a bad worst case, mutates the input, and needs the whole array in memory. The heap is slower by a log factor but is stable in cost, touches each element once, and works on a stream you can never hold all at once. Interviewers usually want you to know both and to say which you would ship — and for streaming data there is no contest.

Train the reflex: when a question asks for a few extremes rather than a full ordering, do not reach for sort. Ask which single element you would want to throw away next, put that element at the root of a heap, and let the rest of the data flow past.