Kth Smallest Element Using Min Heap in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

What is the output of the following Rust code that finds the 3rd smallest element using a min heap?

DSA Rust

use std::collections::BinaryHeap;

fn kth_smallest(nums: &[i32], k: usize) -> i32 {
    let mut min_heap = BinaryHeap::new();
    for &num in nums {
        min_heap.push(-num); // Using max heap as min heap by negating
    }
    let mut result = 0;
    for _ in 0..k {
        result = -min_heap.pop().unwrap();
    }
    result
}

fn main() {
    let nums = [7, 10, 4, 3, 20, 15];
    let k = 3;
    println!("{}", kth_smallest(&nums, k));
}

A 7

B 3

C 4

D 10

💡 Hint

Remember that the min heap is simulated by negating values in Rust's max heap.

The code negates all numbers to use Rust's max heap as a min heap. Popping three times gives the 3rd smallest element, which is 7.

🧠 Conceptual

intermediate

Understanding Min Heap Behavior in Kth Smallest Element

Which statement correctly describes how a min heap helps find the kth smallest element in an unsorted array?

A A min heap sorts the array internally and returns the kth element directly.

B A min heap always keeps the largest element at the root to quickly find the kth smallest.

C A min heap stores only k elements and discards smaller ones to find the kth smallest.

D A min heap stores all elements and popping k times gives the kth smallest element.

💡 Hint

Think about how popping from a min heap works.

A min heap keeps the smallest element at the root. By inserting all elements and popping k times, the kth smallest element is obtained.

🔧 Debug

advanced

Identify the Error in Kth Smallest Element Code

What error will the following Rust code produce when trying to find the 1st smallest element?

DSA Rust

use std::collections::BinaryHeap;

fn kth_smallest(nums: &[i32], k: usize) -> i32 {
    let mut min_heap = BinaryHeap::new();
    for &num in nums {
        min_heap.push(num); // Incorrect: pushing positive values
    }
    let mut result = 0;
    for _ in 0..k {
        result = min_heap.pop().unwrap();
    }
    result
}

fn main() {
    let nums = [5, 3, 8, 1, 2];
    let k = 1;
    println!("{}", kth_smallest(&nums, k));
}

A The code will print 8, which is the largest element, not the 1st smallest.

B The code will print 1, the 1st smallest element correctly.

C The code will panic at unwrap() because the heap is empty early.

D The code will not compile due to type mismatch.

💡 Hint

Consider how Rust's BinaryHeap orders elements by default.

Rust's BinaryHeap is a max heap by default. Pushing positive values and popping returns largest elements first. So popping once returns the largest (8), not the smallest.

🚀 Application

advanced

Resulting Heap State After Insertions

After inserting the elements [9, 4, 7, 1, 3] into a min heap, what is the printed state of the heap array (assuming a binary heap stored in an array)?

DSA Rust

let mut min_heap = vec![];
let elements = [9, 4, 7, 1, 3];
for &el in &elements {
    min_heap.push(el);
    // Assume heapify-up is called here to maintain min heap property
}
println!("{:?}", min_heap);

A [1, 3, 7, 4, 9]

B [1, 3, 7, 9, 4]

C [1, 4, 7, 9, 3]

D [9, 4, 7, 1, 3]

💡 Hint

Remember min heap property: parent is smaller than children.

After inserting all elements with heapify-up, the min heap array is [1, 3, 7, 9, 4].

❓ Predict Output

expert

Output of Kth Smallest Element Using Min Heap with Duplicates

What is the output of the following Rust code that finds the 5th smallest element in an array with duplicates using a min heap?

DSA Rust

use std::collections::BinaryHeap;

fn kth_smallest(nums: &[i32], k: usize) -> i32 {
    let mut min_heap = BinaryHeap::new();
    for &num in nums {
        min_heap.push(-num);
    }
    let mut result = 0;
    for _ in 0..k {
        result = -min_heap.pop().unwrap();
    }
    result
}

fn main() {
    let nums = [2, 1, 2, 3, 4, 2, 5];
    let k = 5;
    println!("{}", kth_smallest(&nums, k));
}

A 4

B 2

C 3

D 5

💡 Hint

Duplicates count as separate elements when popping from the heap.

The sorted array is [1, 2, 2, 2, 3, 4, 5]. The 5th smallest element is 3.

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