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

Time Complexity: Kth Smallest Element Using Min Heap

O(n + k log n)

Understanding Time Complexity

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

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <queue>
#include <vector>

int kthSmallest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap(nums.begin(), nums.end());
    for (int i = 1; i < k; ++i) {
        minHeap.pop();
    }
    return minHeap.top();
}
    

This code builds a min heap from the list and removes the smallest element k-1 times to find the kth smallest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Removing the smallest element from the min heap (pop operation).
• How many times: The pop operation repeats k-1 times.
• Building the min heap from the array happens once at the start.

How Execution Grows With Input

Building the heap takes time proportional to the size of the list, then each pop takes time related to the heap size.

Input Size (n)	Approx. Operations
10	Build heap ~ O(10), pop k-1 times (each ~ O(log 10))
100	Build heap ~ O(100), pop k-1 times (each ~ O(log 100))
1000	Build heap ~ O(1000), pop k-1 times (each ~ O(log 1000))

Pattern observation: Building heap grows linearly with n, popping grows with k times log n.

Final Time Complexity

Time Complexity: O(n + k log n)

This means the time grows mostly with the size of the list and the number of pops, each pop taking a bit longer as the list grows.

Common Mistake

[X] Wrong: "The time is just O(k) because we pop k times."

[OK] Correct: Each pop operation takes time related to the heap size (log n), not constant time, so total time depends on k times log n plus building the heap.

Interview Connect

Understanding this time complexity helps you explain why using a heap is efficient for finding the kth smallest element compared to sorting the whole list.

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?"