find the kth least frequent element in an array in go

To find the kth least frequent element in an array in Go, we can make use of a hashmap and a min-heap. We can iterate through the array and count the frequency of each element. Once that is done, we can add the elements and their frequency to a min-heap, keeping the heap size less than or equal to k. This heap will then contain the top k least frequent elements. The kth least frequent element will be at the root of the min-heap.

Here's the code to implement the above approach:


main.go
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{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(Element))
}

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

func kthLeastFrequent(nums []int, k int) int {
    freqMap := make(map[int]int)

    // Count frequency of each number
    for _, num := range nums {
        freqMap[num]++
    }

    // Create a heap of k least frequent elements
    h := &MinHeap{}
    heap.Init(h)
    for val, freq := range freqMap {
        if h.Len() < k {
            heap.Push(h, Element{val, freq})
        } else if freq > (*h)[0].Freq {
            heap.Pop(h)
            heap.Push(h, Element{val, freq})
        }
    }

    // kth least frequent element is at the root of the heap
    return (*h)[0].Value
}
1169 chars
49 lines

We first define two custom types: Element to keep track of elements and their frequency, and MinHeap to implement the heap interface. In the kthLeastFrequent function, we count the frequency of each element using a hashmap, then create a heap of k least frequent elements. We achieve this by looping through each key-value pair in the freqMap and checking whether it should be added to the heap. If not, we discard it. Finally, the kth least frequent element is at the root of the heap, so we return (*h)[0].Value.

similar go code snippets

find the kth most common element in an array in go

find the kth least common element in an array in go

find the kth least frequent element in an array in go

find the kth most frequent element in an array in go

remove an element from the middle of an array in go

find the index of an element in an array in go

insert an element into an array at a specific index in go

sort an array in go

remove an element from an array at a specific index in go

remove an element from the beginning of an array in go

related categories