Top K Frequent Elements Using Heap in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top K Frequent Elements with Min-Heap

What is the output of the following Go code that finds the top 2 frequent elements using a min-heap?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Element struct {
	value int
	freq  int
}

type MinHeap []Element

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

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Element))
}

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

func topKFrequent(nums []int, k int) []int {
	freqMap := make(map[int]int)
	for _, num := range nums {
		freqMap[num]++
	}

	h := &MinHeap{}
	heap.Init(h)

	for val, freq := range freqMap {
		heap.Push(h, Element{val, freq})
		if h.Len() > k {
			heap.Pop(h)
		}
	}

	res := make([]int, 0, k)
	for h.Len() > 0 {
		res = append(res, heap.Pop(h).(Element).value)
	}
	return res
}

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

A [1, 2]

B [2, 1]

C [3, 2]

D [1, 3]

💡 Hint

Remember that the min-heap pops the smallest frequency first, so the final slice is built by popping from smallest to largest frequency.

The min-heap keeps the top k frequent elements by frequency. When popping from the heap, elements with smaller frequency come out first. So the result slice is built from least frequent of the top k to most frequent. For the input, frequencies are: 1->3, 2->2, 3->1. The top 2 frequent are 1 and 2. Popping from heap returns 2 first, then 1, so output is [2, 1].

🧠 Conceptual

intermediate

Understanding Heap Usage in Top K Frequent Elements

Why is a min-heap used instead of a max-heap to find the top k frequent elements efficiently?

A Because a min-heap sorts elements in descending order automatically.

B Because a min-heap stores elements in increasing order of their values, not frequency.

C Because a max-heap cannot be implemented efficiently in Go.

D Because a min-heap keeps the smallest frequency at the top, allowing easy removal of less frequent elements when size exceeds k.

💡 Hint

Think about how to maintain only the top k frequent elements while processing all frequencies.

A min-heap keeps the smallest frequency element at the top. When the heap size exceeds k, we remove the smallest frequency element. This way, after processing all elements, the heap contains the k elements with the highest frequencies. Using a max-heap would require storing all elements and then extracting k largest, which is less efficient.

🔧 Debug

advanced

Identify the Error in Heap Implementation

What error will occur when running this Go code snippet that implements a min-heap for top k frequent elements?

DSA Go

type MinHeap []Element

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

A The heap will behave as a max-heap, not a min-heap, causing incorrect top k results.

B Syntax error due to missing pointer receiver in methods.

C Runtime panic due to index out of range in Swap method.

D No error; code works correctly as min-heap.

💡 Hint

Check the Less method logic carefully.

The Less method returns true if h[i].freq > h[j].freq, which makes the heap a max-heap (largest frequency at top). This breaks the logic expecting a min-heap to remove smallest frequency elements first, leading to incorrect results.

❓ Predict Output

advanced

Output of Top K Frequent Elements with Equal Frequencies

What is the output of this Go code when multiple elements have the same frequency?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Element struct {
	value int
	freq  int
}

type MinHeap []Element

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool {
	if h[i].freq == h[j].freq {
		return h[i].value > h[j].value
	}
	return h[i].freq < h[j].freq
}
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Element))
}

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

func topKFrequent(nums []int, k int) []int {
	freqMap := make(map[int]int)
	for _, num := range nums {
		freqMap[num]++
	}

	h := &MinHeap{}
	heap.Init(h)

	for val, freq := range freqMap {
		heap.Push(h, Element{val, freq})
		if h.Len() > k {
			heap.Pop(h)
		}
	}

	res := make([]int, 0, k)
	for h.Len() > 0 {
		res = append(res, heap.Pop(h).(Element).value)
	}
	return res
}

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

A [3, 4, 1]

B [1, 2, 3]

C [3, 2, 1]

D [4, 3, 2]

💡 Hint

When frequencies tie, the element with larger value is considered smaller in heap order.

The Less method breaks ties by comparing values in descending order (h[i].value > h[j].value). This means among equal frequencies, elements with larger value are popped first. Frequencies are: 4->2, 1->2, 2->2, 3->1. The top 3 frequent are 4,1,2. The heap pops the smallest frequency first, so 3 (freq 1) is popped last and not in top 3. The result after popping heap is [3, 2, 1].

🚀 Application

expert

Optimizing Top K Frequent Elements for Large Data

You have a very large list of integers and want to find the top 5 frequent elements efficiently. Which approach is best to optimize memory and speed?

A Use a hash map to count frequencies, then a min-heap of size 5 to keep top elements while iterating over the map.

B Sort the entire list and then count frequencies by scanning, finally pick top 5 elements.

C Use a max-heap containing all unique elements and pop top 5 elements after building it.

D Use a balanced binary search tree to store frequencies and extract top 5 elements.

💡 Hint

Consider both time and space complexity for large input.

Using a hash map to count frequencies is O(n). Maintaining a min-heap of fixed size k=5 while iterating over the frequency map keeps memory usage low and insertion/removal operations are O(log k). Sorting the entire list or using a max-heap of all unique elements is less efficient for large data. Balanced trees add overhead and are slower than heaps for this use case.