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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

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

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

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

func main() {
	nums := []int{7, 10, 4, 3, 20, 15}
	k := 3
	fmt.Println(kthSmallest(nums, k))
}

A 7

B 4

C 10

D 3

💡 Hint

Remember the min heap always pops the smallest element first.

The sorted order of the array is [3, 4, 7, 10, 15, 20]. The 3rd smallest element is 7.

❓ Predict Output

intermediate

Result of Kth Smallest Element with Duplicate Values

What will be the output of this Go code finding the 4th smallest element using a min heap with duplicates?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

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

func main() {
	nums := []int{5, 3, 3, 1, 2, 2, 4}
	k := 4
	fmt.Println(kthSmallest(nums, k))
}

A 4

B 2

C 3

D 5

💡 Hint

Duplicates are counted separately in the heap pops.

Sorted array with duplicates: [1, 2, 2, 3, 3, 4, 5]. The 4th smallest is 3.

🔧 Debug

advanced

Identify the Error in Kth Smallest Element Code

What error will this Go code produce when trying to find the 2nd smallest element using a min heap?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

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

func main() {
	nums := []int{8, 3, 5, 1}
	k := 2
	fmt.Println(kthSmallest(nums, k))
}

A 7

B No error, output is 5

C 1

D 3

💡 Hint

Check the Less function in the heap interface.

The Less function is reversed, so the heap acts as a max heap. The 2nd pop returns 5, which is the 2nd smallest in a max heap of all elements.

❓ Predict Output

advanced

Output of Kth Smallest Element with Partial Heap Push

What is the output of this Go code that pushes only first k elements into the min heap and then processes the rest?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func kthSmallest(nums []int, k int) int {
	h := &IntHeap{}
	for i := 0; i < k; i++ {
		heap.Push(h, nums[i])
	}
	heap.Init(h)
	for i := k; i < len(nums); i++ {
		if nums[i] < (*h)[0] {
			(*h)[0] = nums[i]
			heap.Fix(h, 0)
		}
	}
	return (*h)[0]
}

func main() {
	nums := []int{12, 3, 5, 7, 19}
	k := 2
	fmt.Println(kthSmallest(nums, k))
}

A 3

B 7

C 12

D 5

💡 Hint

Trace the heap state after each operation.

Pushes first 2: 12 then 3, heap [3,12]. Init no change. Then 5<3? No; 7<3 No; 19<3 No. Root remains 3.

🚀 Application

expert

Kth Smallest Element in a Stream Using Min Heap

You want to find the kth smallest element in a stream of integers arriving one by one. Which approach using a min heap is correct to maintain the kth smallest element efficiently?

A Keep a min heap of all elements seen so far and pop k times to get kth smallest each time.

B Keep a max heap of all elements and pop k times to get kth smallest element.

C Keep a min heap of size k with the k largest elements seen so far; if new element is larger than heap root, replace root and heapify.

D Keep a max heap of size k with the k smallest elements seen so far; if new element is smaller than heap root, replace root and heapify.

💡 Hint

To efficiently track kth smallest, keep only k elements in the heap.

Maintaining a max heap of size k with the k smallest elements allows efficient updates and retrieval of kth smallest element as the root.

Practice

1. What does a min heap help you find efficiently when looking for the kth smallest element in a list?

easy

A. The smallest elements in order

B. The largest elements in order

C. The middle element only

D. The sum of all elements

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the top (root).

2. Step 2: Use min heap to find kth smallest

   By extracting the root k times, you get the kth smallest element.

3. Final Answer:

   The smallest elements in order -> Option A

4. Quick Check:

   Min heap = smallest elements first [OK]

Hint: Min heap root is always the smallest element [OK]

Common Mistakes:

• Confusing min heap with max heap
• Thinking min heap gives largest elements first
• Assuming kth smallest is the middle element

2. Which of the following Go code snippets correctly creates a min heap from a slice of integers nums using container/heap package?

easy

A. heap.Init(IntHeap(&nums))

B. heap.Init(nums)

C. heap.Init(&nums)

D. heap.Init(&IntHeap(nums))

Solution

1. Step 1: Understand heap.Init usage

   heap.Init requires a pointer to a type implementing heap.Interface.

2. Step 2: Convert slice to IntHeap and pass pointer

   We must convert nums to IntHeap and pass its pointer: &IntHeap(nums).

3. Final Answer:

   heap.Init(&IntHeap(nums)) -> Option D

4. Quick Check:

   heap.Init needs pointer to heap.Interface [OK]

Hint: Pass pointer to heap.Interface type for heap.Init [OK]

Common Mistakes:

• Passing slice directly without conversion
• Passing value instead of pointer
• Using wrong type conversion syntax

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

package main

import (
  "container/heap"
  "fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
  *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func main() {
  nums := []int{7, 10, 4, 3, 20, 15}
  h := IntHeap(nums)
  heap.Init(&h)
  k := 3
  var kthSmallest int
  for i := 0; i < k; i++ {
    kthSmallest = heap.Pop(&h).(int)
  }
  fmt.Println(kthSmallest)
}

medium

A. 10

B. 7

C. 4

D. 3

Solution

1. Step 1: Build min heap from nums

   Heap after init: [3, 7, 4, 10, 20, 15] (smallest at root)

2. Step 2: Pop 3 times to get 3rd smallest

   Pop 1: 3, Pop 2: 4, Pop 3: 7

3. Final Answer:

   7 -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Not popping k times
• Confusing min heap with max heap
• Incorrect heap initialization

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

nums := []int{5, 3, 8, 1}
h := IntHeap(nums)
heap.Init(h)
k := 2
for i := 0; i < k; i++ {
  val := heap.Pop(&h).(int)
  if i == k-1 {
    fmt.Println(val)
  }
}

medium

A. heap.Init should receive &h, not h

B. Pop should be called with h, not &h

C. k should be 3 to get 2nd smallest

D. nums slice should be sorted before heap.Init

Solution

1. Step 1: Check heap.Init argument

   heap.Init requires a pointer to the heap, so it should be heap.Init(&h).

2. Step 2: Confirm other calls are correct

   heap.Pop correctly uses &h, and k=2 is correct for 2nd smallest.

3. Final Answer:

   heap.Init should receive &h, not h -> Option A

4. Quick Check:

   heap.Init needs pointer to heap [OK]

Hint: Always pass pointer to heap in heap.Init [OK]

Common Mistakes:

• Passing value instead of pointer to heap.Init
• Confusing Pop argument
• Incorrect k value for kth smallest

5. Given a large unsorted array of integers, which approach is most efficient to find the 5th smallest element using heaps in Go? A) Build a min heap of all elements and pop 5 times. B) Build a max heap of size 5 and iterate through array. C) Sort the array and pick the 5th element. D) Use a min heap but pop all elements until the 5th smallest is found.

hard

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

B. Sort the array and pick the 5th element.

C. Build a max heap of size 5 and iterate through array.

D. Use a min heap but pop all elements until the 5th smallest is found.

Solution

1. Step 1: Understand efficiency of building full min heap

   Building a min heap of all elements and popping 5 times is O(n + k log n), which can be costly for large n.

2. Step 2: Use max heap of size k for better efficiency

   Maintaining a max heap of size 5 while iterating keeps track of 5 smallest elements efficiently in O(n log k).

3. Step 3: Compare other options

   Sorting is O(n log n), popping all elements is inefficient, so max heap size k is best.

4. Final Answer:

   Build a max heap of size 5 and iterate through array. -> Option C

5. Quick Check:

   Max heap size k = efficient kth smallest [OK]

Hint: Use max heap of size k for kth smallest in large arrays [OK]

Common Mistakes:

• Building full min heap for large arrays
• Sorting entire array unnecessarily
• Popping all elements from min heap