Kth Largest Element Using Max Heap in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Max Heap after inserting elements

What is the printed state of the max heap after inserting the elements [3, 1, 5, 12, 10] in that order?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

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

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

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

func main() {
	h := &MaxHeap{}
	heap.Init(h)
	elements := []int{3, 1, 5, 12, 10}
	for _, v := range elements {
		heap.Push(h, v)
	}
	fmt.Println(*h)
}

A [10 12 5 3 1]

B [12 10 5 1 3]

C [12 10 5 3 1]

D [5 3 1 10 12]

💡 Hint

Remember that in a max heap, the largest element is at the root and the heap property is maintained after each insertion.

The max heap property ensures the largest element is at the root. After inserting 3,1,5,12,10, the heap array representation is [12 10 5 3 1].

❓ Predict Output

intermediate

Output after extracting max element from max heap

Given a max heap represented as [20, 15, 18, 8, 10, 5], what is the heap state after one Pop operation?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

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

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

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

func main() {
	h := &MaxHeap{20, 15, 18, 8, 10, 5}
	heap.Init(h)
	heap.Pop(h)
	fmt.Println(*h)
}

A [15 10 5 8]

B [18 15 5 8 10]

C [15 18 10 8 5]

D [18 15 10 8 5]

💡 Hint

Pop removes the root (max) and then heapifies to maintain max heap property.

After popping 20, the heap reorders to maintain max heap property resulting in [18 15 10 8 5].

🧠 Conceptual

advanced

Understanding Kth Largest Element Extraction

If you want to find the 3rd largest element using a max heap built from an array, which of the following steps is correct?

A Build a max heap, then pop the max element 3 times; the last popped element is the 3rd largest.

B Build a max heap, then pop the max element once; the root is the 3rd largest.

C Build a max heap, then pop the max element 2 times; the next root is the 3rd largest.

D Build a max heap, then pop the max element 4 times; the last popped element is the 3rd largest.

💡 Hint

Think about how many times you remove the largest element to reach the kth largest.

Popping the max element k times removes the top k largest elements. The kth popped element is the kth largest.

🔧 Debug

advanced

Identify the error in Kth largest element code snippet

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

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

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

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

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

func main() {
	h := &MaxHeap{10, 5, 20, 8}
	heap.Init(h)
	heap.Pop(h)
	next := (*h)[0]
	fmt.Println(next)
}

A Prints 10

B Prints 20

C Prints 5

D Runtime panic: index out of range

💡 Hint

Check the Less function for max heap property correctness.

Less function uses < which creates a min heap, so after popping max (which is actually min), the root is 10, not the max.

🚀 Application

expert

Find the 4th largest element using max heap operations

Given the array [7, 10, 4, 3, 20, 15], what is the 4th largest element after building a max heap and popping the max element 4 times?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

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

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

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

func main() {
	h := &MaxHeap{}
	elements := []int{7, 10, 4, 3, 20, 15}
	for _, v := range elements {
		heap.Push(h, v)
	}
	heap.Init(h)
	var kthLargest int
	for i := 0; i < 4; i++ {
		kthLargest = heap.Pop(h).(int)
	}
	fmt.Println(kthLargest)
}

A 15

B 7

C 4

D 10

💡 Hint

Pop the max element 4 times and track the last popped value.

The popped elements in order are 20, 15, 10, 7. The 4th largest is 7.

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Build a max heap from the array and extract the maximum element k times.

B. Build a min heap and extract the minimum element k times.

C. Sort the array and pick the kth element from the start.

D. Use a hash map to count frequencies and find the kth largest.

Solution

1. Step 1: Understand max heap property

   A max heap always keeps the largest element at the root, so extracting the root gives the current largest element.

2. Step 2: Extract max k times

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

3. Final Answer:

   Build a max heap and extract max k times -> Option A

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to get kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Confusing kth largest with kth smallest

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

easy

A. heap.Init(&arr) // arr is []int

B. heap.Pop(arr) // arr is []int

C. heap.Push(arr, value) // arr is []int

D. heap.Init(&maxHeap) // maxHeap implements heap.Interface with max-heap logic

Solution

1. Step 1: Understand Go heap package usage

   The Go heap package requires a type implementing heap.Interface to define heap behavior (min or max).

2. Step 2: Use a custom maxHeap type

   To create a max heap, define a type with Len, Less (inverted for max), Swap, Push, Pop methods, then call heap.Init(&maxHeap).

3. Final Answer:

   heap.Init(&maxHeap) where maxHeap implements max-heap interface -> Option D

4. Quick Check:

   Custom heap.Interface needed for max heap [OK]

Hint: Use custom type implementing heap.Interface for max heap [OK]

Common Mistakes:

• Calling heap.Init on a plain slice
• Not implementing Less method for max heap
• Using heap.Push/Pop directly on slice

3. What is the output of the following Go code snippet that finds the 3rd largest element using a max heap?

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

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

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

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

func main() {
	arr := []int{4, 1, 7, 3, 8, 5}
	h := MaxHeap(arr)
	heap.Init(&h)

	var kthLargest int
	for i := 0; i < 3; i++ {
		kthLargest = heap.Pop(&h).(int)
	}
	fmt.Println(kthLargest)
}

medium

A. 4

B. 5

C. 7

D. 3

Solution

1. Step 1: Build max heap from array

   Array is [4,1,7,3,8,5]. Max heap root is 8, next largest 7, then 5, etc.

2. Step 2: Pop max 3 times

   First pop: 8, second pop: 7, third pop: 5. The 3rd largest is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   3rd largest element = 5 [OK]

Hint: Pop max heap k times; last popped is kth largest [OK]

Common Mistakes:

• Confusing 3rd largest with 2nd largest
• Not building max heap correctly
• Off-by-one errors in loop

4. Identify the error in this Go code snippet that tries to find the 2nd largest element using a max heap:

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

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

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

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

func main() {
	arr := []int{10, 20, 15, 30, 40}
	h := MaxHeap(arr)
	heap.Init(&h)

	heap.Pop(&h)
	secondLargest := heap.Pop(&h).(int)
	fmt.Println(secondLargest)
}

medium

A. Push method does not append correctly.

B. Pop method returns wrong element from the heap.

C. Less method uses < instead of >, so heap is min heap not max heap.

D. heap.Init is called on a slice, not a heap.Interface.

Solution

1. Step 1: Check Less method for heap type

   Less uses < which creates a min heap, but we want a max heap for kth largest.

2. Step 2: Effect on extraction

   Extracting twice from min heap gives 10 and 15, not the largest elements.

3. Final Answer:

   Less method uses < instead of >, making it a min heap -> Option C

4. Quick Check:

   Less method defines heap type [OK]

Hint: Max heap Less must use >, not < [OK]

Common Mistakes:

• Using < in Less for max heap
• Not implementing heap.Interface fully
• Calling heap.Init on plain slice

5. Given a large array of integers, which approach is most efficient to find the 5th largest element using a heap in Go, considering time and space complexity?

hard

A. Build a min heap of size 5 and iterate through array, replacing root if element is larger.

B. Build a max heap of the entire array and pop 5 times.

C. Sort the entire array and pick the 5th largest element.

D. Use a hash map to count frequencies and find the 5th largest.

Solution

1. Step 1: Compare approaches for large arrays

   Building a max heap of entire array is O(n), popping 5 times is O(k log n). Sorting is O(n log n).

2. Step 2: Use min heap of size 5 for efficiency

   Maintaining a min heap of size 5 keeps track of top 5 largest elements in O(n log k) time and O(k) space, which is efficient.

3. Final Answer:

   Use a min heap of size 5 and replace root when larger element found -> Option A

4. Quick Check:

   Min heap size k for kth largest is efficient [OK]

Hint: Use min heap of size k for efficient kth largest in large data [OK]

Common Mistakes:

• Building max heap of entire array wastes space/time
• Sorting entire array is slower for large data
• Using hash map does not help with order