find the kth least frequent element in an array in python

One approach to find the kth least frequent element in an array would involve using a dictionary to count the frequency of each element, and a min heap to keep track of the k least frequent elements.

Here's an implementation in Python:

main.py
from typing import List
from collections import Counter
import heapq

def kth_least_frequent(nums: List[int], k: int) -> int:
    counter = Counter(nums)
    min_heap = [(freq, num) for num, freq in counter.items()]

    # heapify the min heap
    heapq.heapify(min_heap)

    # pop the k-1 least frequent elements from the heap
    for i in range(k-1):
        heapq.heappop(min_heap)

    # return the kth least frequent element
    return heapq.heappop(min_heap)[1]
469 chars
18 lines

We first count the frequency of each element using a Counter dictionary. We then create a min heap of tuples, where each tuple contains the frequency and the corresponding element. We heapify the min heap using heapq.heapify.

Next, we pop the k-1 least frequent elements from the heap using heapq.heappop, leaving only the kth least frequent element on top of the heap. Finally, we return the element from the top of the heap.

The time complexity of this approach is O(n log k) for building the heap and popping the k-1 least frequent elements. The space complexity is O(n) for the dictionary and the heap.