Kth Smallest Element Using Min Heap in DSA Rust - 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 grow when the list or k gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::collections::BinaryHeap;

fn kth_smallest(nums: &[i32], k: usize) -> i32 {
    let mut min_heap = BinaryHeap::from(nums.iter().map(|&x| -x).collect::>());
    for _ in 0..k-1 {
        min_heap.pop();
    }
    -*min_heap.peek().unwrap()
}
    

This code builds a min heap by negating values and then pops k-1 times to get the kth smallest element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Building the heap from all elements and popping k-1 times.
• How many times: Heap built once over n elements; pop operation repeated k-1 times.

How Execution Grows With Input

Building the heap takes time proportional to the number of elements, and each pop takes time depending on heap size.

Input Size (n)	k	Approx. Operations
10	3	Build heap ~10, Pops 2 times
100	10	Build heap ~100, Pops 9 times
1000	100	Build heap ~1000, Pops 99 times

Pattern observation: Building heap grows linearly with n; popping grows linearly with k, each pop costs log n.

Final Time Complexity

Time Complexity: O(n + k log n)

This means the time grows mostly by building the heap once, then popping k times, each pop taking logarithmic time.

Common Mistake

[X] Wrong: "Popping k times from the heap is O(k) because each pop is constant time."

[OK] Correct: Each pop requires reordering the heap, which takes O(log n) time, so total pop time is O(k log n).

Interview Connect

Understanding this time complexity helps you explain how heap operations affect performance and shows you can analyze combined steps clearly.

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

Practice

1. What is the main idea behind finding the kth smallest element using a min heap?

easy

A. Use a hash map to count frequencies and find the kth smallest

B. Sort the array and pick the element at index k

C. Build a max heap and extract the maximum element k times

D. Build a min heap from the array and extract the minimum element k times

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so extracting the root gives the smallest element.

2. Step 2: Extract minimum k times

   By removing the root k times, the last extracted element is the kth smallest.

3. Final Answer:

   Build a min heap and extract minimum k times -> Option D

4. Quick Check:

   Min heap extraction = kth smallest element [OK]

Hint: Extract min from min heap k times to get kth smallest [OK]

Common Mistakes:

• Using max heap instead of min heap
• Sorting array instead of using heap
• Confusing kth smallest with kth largest

2. Which Rust code snippet correctly creates a min heap from a vector nums?

easy

A. let mut heap = std::collections::BinaryHeap::from(nums.iter().map(|&x| Reverse(x)).collect::());

B. let mut heap = std::collections::BinaryHeap::from(nums);

C. let mut heap = std::collections::BinaryHeap::new(); for &num in &nums { heap.push(num); }

D. let mut heap = nums.sort();

Solution

1. Step 1: Understand Rust's BinaryHeap default behavior

   Rust's BinaryHeap is a max heap by default, so to create a min heap, we wrap elements with Reverse.

2. Step 2: Use Reverse wrapper to invert order

   Mapping each element to Reverse(x) and collecting into a vector allows building a min heap.

3. Final Answer:

   Use BinaryHeap with Reverse wrapper on elements -> Option A

4. Quick Check:

   BinaryHeap + Reverse = min heap in Rust [OK]

Hint: Wrap elements with Reverse to make min heap in Rust [OK]

Common Mistakes:

• Using BinaryHeap directly creates max heap
• Sorting vector does not create a heap
• Forgetting to collect after map

3. What is the output of the following Rust code snippet?

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    let nums = vec![7, 10, 4, 3, 20, 15];
    let k = 3;
    let mut heap = BinaryHeap::from(nums.iter().map(|&x| Reverse(x)).collect::());
    let mut kth_smallest = 0;
    for _ in 0..k {
        if let Some(Reverse(val)) = heap.pop() {
            kth_smallest = val;
        }
    }
    println!("{}", kth_smallest);
}

medium

A. 7

B. 10

C. 4

D. 3

Solution

1. Step 1: Build min heap from nums

   The min heap contains elements: 3, 4, 7, 10, 15, 20 with 3 at root.

2. Step 2: Extract min 3 times

   Extracted elements in order: 3 (1st), 4 (2nd), 7 (3rd). The 3rd extracted is 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   3rd smallest in [7,10,4,3,20,15] = 7 [OK]

Hint: Extract min k times from min heap to get kth smallest [OK]

Common Mistakes:

• Confusing kth smallest with kth largest
• Not using Reverse wrapper for min heap
• Off-by-one error in loop

4. Identify the error in this Rust code snippet that tries to find the 2nd smallest element using a min heap:

use std::collections::BinaryHeap;

fn main() {
    let nums = vec![5, 3, 8, 1];
    let k = 2;
    let mut heap = BinaryHeap::from(nums);
    let mut kth_smallest = 0;
    for _ in 0..k {
        if let Some(val) = heap.pop() {
            kth_smallest = val;
        }
    }
    println!("{}", kth_smallest);
}

medium

A. The loop should run from 1 to k inclusive

B. BinaryHeap creates a max heap, so it finds kth largest, not smallest

C. The vector nums is empty, causing runtime error

D. The variable kth_smallest is not initialized

Solution

1. Step 1: Check heap type created by BinaryHeap::from

   BinaryHeap in Rust is a max heap by default, so it pops largest elements first.

2. Step 2: Understand effect on kth smallest search

   Extracting from max heap gives kth largest, not kth smallest, so result is incorrect.

3. Final Answer:

   BinaryHeap creates max heap, finds kth largest not smallest -> Option B

4. Quick Check:

   BinaryHeap default = max heap [OK]

Hint: Rust BinaryHeap is max heap by default, use Reverse for min heap [OK]

Common Mistakes:

• Assuming BinaryHeap is min heap
• Incorrect loop range
• Ignoring Reverse wrapper

5. Given a large vector nums with 1 million elements, which approach is most efficient to find the 10th smallest element using a min heap in Rust?

hard

A. Build a min heap of all elements and pop 10 times

B. Use a hash map to count frequencies and find 10th smallest

C. Build a max heap of size 10 and iterate over nums pushing elements

D. Sort the entire vector and pick element at index 9

Solution

1. Step 1: Analyze building min heap of all elements

   Building min heap of 1 million elements uses O(n) time but popping 10 times is O(k log n), still costly in memory and time.

2. Step 2: Use max heap of size k to track smallest elements

   Maintaining a max heap of size 10 while iterating allows efficient O(n log k) time and less memory.

3. Step 3: Sorting entire vector is O(n log n), slower than heap approach

   Sorting 1 million elements is expensive compared to heap of size 10.

4. Final Answer:

   Build max heap of size 10 and iterate over nums pushing elements -> Option C

5. Quick Check:

   Max heap size k = efficient kth smallest [OK]

Hint: Use max heap of size k for large data to find kth smallest [OK]

Common Mistakes:

• Building min heap of all elements wastes memory
• Sorting entire vector is slower
• Using hash map is unnecessary overhead