Given an unsorted array, return the kth largest element. Discuss time complexity.
Skip to solutionKEEP THE
01
Understand the problem
dsaheaparrays
02
Attempt it yourself
Sketch your approach before reading the solution — that's what interviews test.
Nudge consolestandby
Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.
03
Study the solution
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.
Solution ready — 2 min read
Classified // press E to declassify
04
Read the code
Min-heap of size k
Run Playgroundimport 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)) # 405
Join the discussion
Discussion (0)
Sign in to join the discussion.
No responses yet. Be the first to share what you think.
Transmission complete // awaiting log
KEEP THE
STREAK ALIVE.
Dossier 47 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.