$$ \newcommand\Tr{\mathrm{Tr}} \newcommand{\braket}[2]{\langle #1 \mid #2 \rangle} \newcommand\I{\mathbb{I}} \newcommand{\avg}[1]{\left< #1 \right>} \newcommand{\RD}{D} \newcommand{\ri}{\mathrm{i}} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\Sign}{Sign} \newcommand{\ii}{\mathrm i} \newcommand{\vv}{\mathrm v} \newcommand{\ff}{\mathrm f} \newcommand{\mm}{\mathrm m} \newcommand{\ee}{\mathrm e} \newcommand{\xx}{\mathrm x} \newcommand{\RR}{\mathrm R} \newcommand{\dd}{\mathrm d} \newcommand{\FF}{\mathrm F} \newcommand{\BB}{\mathrm B} \newcommand{\vph}{v_{\mathrm{ph}}} $$

Top K Frequent Elements

Problem

Given an array of integer and integer K, our task is to find the K most frequent elements in the Array. The K most frequent elements can be in any order.
For example,

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: The 2 most frequent elements are [1,2]. [2,1] is also a valid output because the output doesn't have to be sorted.
Input: nums = [1], k = 1
Output: 1
Explanation: The 1 most frequent elements is only 1.

Solution

Priority Queue (Heap)

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    nums.forEach {
        map[it] = map.getOrDefault(it, 0) + 1
    }

    val priorityQueue = PriorityQueue<Pair<Int, Int>>(
        compareByDescending { it.second }
    )
    map.forEach {
        priorityQueue.add(Pair(first = it.key, second = it.value))
    }

    val result = IntArray(k)
    var i = 0
    while (i < k && priorityQueue.isNotEmpty()) {
        result[i] = priorityQueue.remove().first
        i++
    }

    return result
}

class ElementFrequency {
    private int element;
    private int frequency;

    public ElementFrequency(int element, int frequency) {
        this.element = element;
        this.frequency = frequency;
    }

    public int getFrequency() {
        return this.frequency;
    }
}

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    PriorityQueue<ElementFrequency> priorityQueue = new PriorityQueue<>(
            Comparator.comparing(ElementFrequency::getFrequency).reversed()
    );
    map.forEach((key, value) -> {
                priorityQueue.add(new ElementFrequency(key, value));
            }
    );

    int[] result = new int[k];
    int i = 0;
    while (i < k && !priorityQueue.isEmpty()) {
        result[i] = priorityQueue.remove().element;
        i++;
    }

    return result;      
}

Quickselect

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    nums.forEach {
        map[it] = map.getOrDefault(it, 0) + 1
    }

    val arr = Array<Pair<Int, Int>>(map.size) { Pair(first = 0, second = 0) }
    var i = 0
    map.forEach {
        arr[i] = Pair(first = it.key, second = it.value)
        i++
    }

    quickSelect(arr, map.size - k, 0, map.size - 1)
    val result = IntArray(k)
    i = 0
    while (i < k) {
        result[i] = arr[arr.size - 1 - i].first
        i++
    }
    return result
}

private fun quickSelect(nums: Array<Pair<Int, Int>>, k: Int, low: Int, high: Int) {
    if (low == high) return

    val position: Int = hoarePartition(nums, low, high)
    return if (k <= position) quickSelect(nums, k, low, position) else quickSelect(nums, k, position + 1, high)
}

private fun hoarePartition(nums: Array<Pair<Int, Int>>, low: Int, high: Int): Int {
    val pivot = nums[(low + high) / 2].second

    var i = low - 1
    var j = high + 1
    while (true) {
        do {
            i++
        } while (nums[i].second < pivot)
        do {
            j--
        } while (nums[j].second > pivot)

        if (i >= j) return j

        nums[i] = nums[j].also {
            nums[j] = nums[i]
        }
    }
}

class ElementFrequency {
    private int element;
    private int frequency;

    public ElementFrequency(int element, int frequency) {
        this.element = element;
        this.frequency = frequency;
    }

    public int getFrequency() {
        return this.frequency;
    }
}

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    ElementFrequency[] arr = new ElementFrequency[map.size()];
    int i = 0;
    for (Integer key : map.keySet()) {
        arr[i] = new ElementFrequency(key, map.get(key));
        i++;
    }

    quickSelect(arr, map.size() - k, 0, map.size() - 1);
    int[] result = new int[k];
    i = 0;
    while (i < k) {
        result[i] = arr[arr.length - 1 - i].element;
        i++;
    }

    return result;
}

private void quickSelect(ElementFrequency[] nums, int k, int low, int high) {
    if (low == high) return;

    int position = hoarePartition(nums, low, high);
    if (k <= position)
        quickSelect(nums, k, low, position);
    else
        quickSelect(nums, k, position + 1, high);
}

private int hoarePartition(ElementFrequency[] nums, int low, int high) {
    int pivot = nums[(low + high) / 2].frequency;

    int i = low - 1;
    int j = high + 1;
    while (true) {
        do {
            i++;
        } while (nums[i].frequency < pivot);
        do {
            j--;
        } while (nums[j].frequency > pivot);

        if (i >= j) return j;

        ElementFrequency temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Bucket Sort

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    var min = nums[0]
    var max = nums[0]
    for (num in nums) {
        if (num > max) max = num else if (num < min) min = num
    }

    val frequencies = IntArray(max - min + 1)
    for (num in nums) {
        frequencies[num - min]++
    }

    val buckets = arrayOfNulls<ArrayList<Int>>(nums.size + 1)
    for (i in frequencies.indices) {
        val num = i + min
        val frequency = frequencies[i]
        if (buckets[frequency] == null) {
            buckets[frequency] = ArrayList()
        }
        buckets[frequency]!!.add(num)
    }

    var k = k
    val result = IntArray(k)
    var i = buckets.size - 1
    while (k > 0) {
        buckets[i]?.let {
            for (num in buckets[i]!!) {
                k -= 1;
                result[k] = num;
                if (k == 0) {
                    break;
                }
            }
        }
        i--
    }

    return result
}

public int[] topKFrequent(int[] nums, int k) {
    int min = nums[0], max = nums[0];
    for (int num : nums) {
        if (num > max)
            max = num;
        else if (num < min)
            min = num;
    }

    int[] frequencies = new int[max - min + 1];
    for (int num : nums) {
        frequencies[num - min]++;
    }

    List<Integer>[] buckets = new List[nums.length + 1];
    for (int i = 0; i < frequencies.length; i++) {
        int num = i + min;
        int frequency = frequencies[i];
        if (buckets[frequency] == null) {
            buckets[frequency] = new ArrayList<>();
        }
        buckets[frequency].add(num);
    }

    int[] result = new int[k];
    for (int i = buckets.length - 1; k > 0; i--) {
        if (buckets[i] != null) {
            for (int num : buckets[i]) {
                k -= 1;
                result[k] = num;
                if (k == 0) {
                    break;
                }
            }
        }
    }

    return result;     
}