Coding Interview Preparation on Telegram: “🎯 CODING CHALLENGE #7

🎯 CODING CHALLENGE #7 - Kth Largest Element in an Array
Difficulty: Medium | Asked at: Facebook, Amazon, Google


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

💡 Hint: Sorting works but is O(n log n). Can you do better with a heap that only ever holds k elements?

Solution (min-heap approach):

python
import heapq

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)

    return heap[0]

Complexity: O(n log k) time, O(k) space - much better than sorting when k is small relative to n.

Common mistake: Using a max-heap of the FULL array (heapifying all n elements, then popping k times) - this works, but it's a weaker answer. Building a min-heap of just size k and comparing incoming elements against the smallest kept element is the optimization interviewers are hoping to see.

Alternative: Quickselect gets this down to average O(n) time, though worst case O(n²) - a great follow-up to mention if you want to show extra depth.

Do you know Quickselect, or is the heap approach your default here? 👇