Kth Largest Element Using Max Heap in DSA Go - Time & Space Complexity

Time Complexity: Kth Largest Element Using Max Heap

O(n log n + k log n)

Understanding Time Complexity

We want to understand how long it takes to find the kth largest number using a max heap.

How does the time needed grow as the list of numbers gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func findKthLargest(nums []int, k int) int {
    maxHeap := &MaxHeap{}
    for _, num := range nums {
        maxHeap.Insert(num)
    }
    var kthLargest int
    for i := 0; i < k; i++ {
        kthLargest = maxHeap.ExtractMax()
    }
    return kthLargest
}
    

This code builds a max heap from the list, then removes the largest element k times to find the kth largest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting each number into the max heap and extracting the max element.
• How many times: Insert runs once for each of n numbers; ExtractMax runs k times.

How Execution Grows With Input

As the list size n grows, inserting all numbers takes more time, and extracting k times adds extra work.

Input Size (n)	Approx. Operations
10	About 10 insertions + k extractions
100	About 100 insertions + k extractions
1000	About 1000 insertions + k extractions

Pattern observation: Insertion cost grows roughly with n log n, extraction cost grows with k log n.

Final Time Complexity

Time Complexity: O(n log n + k log n)

This means the time grows mostly by n times log n for building the heap, plus k times log n for removing elements.

Common Mistake

[X] Wrong: "Building the heap is just O(n) so total time is O(n + k log n)."

[OK] Correct: While heap construction can be O(n), inserting elements one by one as here costs O(n log n), which dominates the time.

Interview Connect

Understanding this time complexity helps you explain your approach clearly and shows you know how data structures affect performance.

Self-Check

"What if we used a min heap of size k instead of a max heap of size n? How would the time complexity change?"