Kth Largest Element

Table of Contents +

This one looks easy at first. The interviewer hands you a messy list of numbers and asks for the kth largest. So your first thought is “just sort it and pick”. That works. But the real thing being tested is whether you can do better than sorting the whole array when you only care about a few of the top numbers. See, if you only need the 3rd largest, why bother ordering all million numbers? That is the question hiding behind this problem.

🔄 The Problem

You get an unsorted array of numbers and a number k. You have to return the kth largest element. Note this is the kth largest by position when sorted, not the kth distinct value. So if the array has repeats, they still count.

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


Explanation: Sorted in descending order it is [6, 5, 4, 3, 2, 1].
The 2nd one is 5.

🐢 The Simple Approach: Sort and Index

The first idea everyone has is to sort the array. Sorting means putting the numbers in order, smallest to largest or largest to smallest.

Once it is sorted from largest to smallest, the kth largest just sits at position k - 1 (because counting starts at zero). Pick it and you are done.

It is correct and easy to explain. The catch is speed. Sorting touches and orders every single number. That costs O(n log n) time. But you only wanted one number near the top. So you did a lot of extra work ordering the bottom part of the array that you never even look at.

🚀 The Better Approach: A Min-Heap of Size k

Here is the smarter idea. Keep a small box that holds only the k largest numbers you have seen so far. This box is a min-heap. A min-heap is a structure where the smallest item is always sitting on top and is quick to look at or remove.

Now think about why a min-heap of size k is perfect here. The box holds the top k numbers. The smallest of those top k numbers is exactly the kth largest. And in a min-heap, that smallest one is right on top. So the answer is always the top of the heap.

We walk through the array once and do this for each number:

  • Push the number into the heap.
  • If the heap now holds more than k numbers, remove the top one. The top is the smallest, so we throw away the smallest and keep the bigger ones.

After we finish the array, the heap holds the k biggest numbers, and its top is the kth largest. Each push or remove on a heap of size k costs about O(log k). We do it n times. So the total is O(n log k). When k is small, that is much faster than sorting everything.

Steps to find the kth largest with a min-heap

  1. Create an empty min-heap.
  2. Go through each number in the array.
  3. Push the current number into the heap.
  4. If the heap size is greater than k, remove the top (the smallest) element.
  5. After the loop ends, the top of the heap is the kth largest. Return it.

Python’s heapq module is a min-heap. We push every number, then pop the smallest whenever the heap grows past k.

kth_largest.py
import heapq


def find_kth_largest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)  # drop the smallest
    return min_heap[0]  # top is the kth largest


nums = [3, 2, 1, 5, 6, 4]
k = 2
print(find_kth_largest(nums, k))

The output of the above code will be:

5

⏱️ Time and Space Complexity

Approach Time Space
Sort and index O(n log n) O(1) to O(n)
Min-heap of size k O(n log k) O(k)
Quickselect O(n) average, O(n²) worst O(1)

There is one more approach worth knowing. It is called quickselect. Quickselect borrows the partition idea from quick sort. It picks a pivot and splits the array, but then it only goes into the one side that holds the answer instead of sorting both sides. On average this reaches the kth largest in O(n) time. The downside is its worst case is O(n²), and it changes the order of the array. So in interviews the heap answer is often the safer choice. We list quickselect here for comparison only and do not code it on this page.

Tip

If the interviewer only wants the kth largest distinct value, first remove duplicates (put the numbers in a set), then apply the same heap idea. Always ask whether duplicates should count before you start coding.

🧩 Key Takeaways

  • ✅ Sorting works and is easy to explain, but it does extra work at O(n log n) when you only need a few top numbers.
  • ✅ A min-heap of size k keeps just the top k numbers, and its smallest item on top is exactly the kth largest.
  • ✅ Each heap step costs O(log k), so the whole scan is O(n log k), which beats sorting when k is small.
  • ✅ Quickselect gives O(n) on average but has an O(n²) worst case and reorders the array.
  • ✅ Always ask if duplicates count as separate elements before you pick your approach.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why does the top of a size-k min-heap give the kth largest element?

    Why: The size-k heap keeps only the top k numbers, so the smallest of those, sitting on top, is the kth largest overall.

  2. 2

    What is the time complexity of the size-k min-heap approach?

    Why: We do n push or pop operations, each costing about O(log k) on a heap of size k, giving O(n log k).

  3. 3

    When the heap size grows past k, what do we remove?

    Why: We pop the top of the min-heap, which is the smallest value, so only the larger numbers stay.

  4. 4

    What is the main drawback of quickselect compared to the heap approach?

    Why: Quickselect averages O(n) but can degrade to O(n²) on bad pivots, and it rearranges the input array in place.

Score: 0 / 4

🚀 What’s Next?

Previous Sort Colors (Dutch National Flag) Next Reverse a Linked List

Share & Connect

Share on LinkedIn