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.