mediumAmazonDSA2024 · 2023 · 2022

Find the kth largest element in an array

Q: Find the kth largest element in an array

**Intuition.** You don't need the array fully sorted — just the kth largest. Keep a **min-heap of size k** holding the k largest values seen so far. Its smallest element (the root) is, by definition, the kth largest. Push every number and pop whenever the heap grows past k. min-heap of size k → its root is the kth largest [3,2,1,5,6,4] k=2 <text x="210" y="80" fill="#22c55e" font-size="11" text-

807 views

Understand the problem

Given an unsorted array, return the kth largest element. Discuss time complexity.

dsaheaparrays

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Min-heap of size k

Run Playground

import heapq

def find_kth_largest(nums, k):
    heap = []                       # min-heap of the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)     # drop the smallest
    return heap[0]                  # root = kth largest


# --- demo ---
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))            # 5
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))   # 4

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you find the maximum subarray sum?

How do you get the right-side view of a binary tree?