Kth Smallest Element Using Min Heap in DSA Go - Time & Space Complexity

Time Complexity: Kth Smallest Element Using Min Heap

O(n log n + k log n)

Understanding Time Complexity

We want to know how the time needed to find the kth smallest number grows as the list gets bigger.

Specifically, how does using a min heap affect the work done as input size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func kthSmallest(nums []int, k int) int {
    h := &MinHeap{}
    heap.Init(h)
    for _, num := range nums {
        heap.Push(h, num)
    }
    var result int
    for i := 0; i < k; i++ {
        result = heap.Pop(h).(int)
    }
    return result
}
    

This code builds a min heap from the input list, then removes the smallest element k times to find the kth smallest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting all elements into the min heap and popping k times.
• How many times: Insert happens n times (once per element), pop happens k times.

How Execution Grows With Input

As the list size n grows, building the heap takes more time, and popping k times adds extra work.

Input Size (n)	Approx. Operations
10	About 10 insertions + k pops, each costing log n steps
100	About 100 insertions + k pops, each costing log 100 steps
1000	About 1000 insertions + k pops, each costing log 1000 steps

Pattern observation: The time grows roughly proportional to n times log n, plus k times log n, which is mostly dominated by n log n when k is smaller than n.

Final Time Complexity

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

This means the time needed grows a bit faster than the size of the list because each insertion and removal takes extra steps related to the heap size.

Common Mistake

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

[OK] Correct: While heap construction can be O(n), each pop operation costs O(log n), and pushing all elements individually costs O(n log n), so total time is dominated by these log n steps.

Interview Connect

Understanding how heaps work and their time costs helps you explain efficient ways to find order statistics like the kth smallest element, a common real-world problem.

Self-Check

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