Top K Frequent Elements

Top K Frequent Elements - Leetcode

You can find the link to the problem- here

First solution with bucket sort and time complexity O(n)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        if(nums.length == 1)
            return nums;

        /**
        *
        * We are using HashMap to store the frequency of numbers 
        * We'll use it in the next steps
        */
        HashMap<Integer, Integer> numsMap = new HashMap<>();
        for(int el: nums) {
            numsMap.put(el, numsMap.getOrDefault(el, 0) + 1);
        }

        /**
        *
        * We create an array of List<Integer> for storing all elements with a certain frequency
        * 
        *
        * If we have more than one element with frequency 2, we'll store those elements
        * at index 2 in our List at that index in buckets array. 
        * We'll repeat the same process for all the possible frequencies, if there are no numbers with a certain 
        * frequency it's List will just point to null
        *
        * NOTE - 
        * The reason for creating an array with a length greater than nums.length is because
        * indexing starts from zero but we want to store elements with indexes starting from one and going till
        * nums. length, that's why we need the size to be greater by one unit.
        *
        */
        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        for(int el: numsMap.keySet()) {
            int freq = numsMap.get(el);
            if(buckets[freq] == null)
                buckets[freq] = new ArrayList<Integer>();
            buckets[freq].add(el);
        }

        /**
        *
        * We're looping through our buckets array in reverse to get all the elements
        * with highest frequencies first.
        *
        * Whenever our list for a certain frequency is null we'll just skip it.
        * However, if we do find a list with values, we'll add those values to result array
        * and increment our index till we exhaust the list of till the index is equal to k
        * 
        */
        int[] result = new int[k];
        int index = 0;

        for(int freq = buckets.length - 1; freq > 0; freq--) {
            if(buckets[freq] == null)
                continue;
            for(int el: buckets[freq]) {
                result[index++] = el;
                if(index == k)
                    return result;
            }

        }

        return result;
    }
}

Second solution using Priority Queue, we follow a similar approach by creating a hashmap with elements and their frequencies. After that, we store our elements in a priority queue with the highest frequency elements having the highest priority. Finally, we just assign top k values to our result array and return the result array.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        if(nums.length == 1)
            return nums;


        HashMap<Integer, Integer> numsMap = new HashMap<>();

        for(int el: nums) {
            if(numsMap.containsKey(el)) {
                int count = numsMap.get(el);
                count++;
                numsMap.put(el, count);
                continue;
            }
            numsMap.put(el, 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->numsMap.get(b) - numsMap.get(a));
        pq.addAll(numsMap.keySet());

        int[] result = new int[k];
        for(int i=0; i<k; i++) {
            result[i] = pq.remove();
        }

        return result;
    }
}

If someone finds any mistake or any opportunity for improvement please do share in the comments, thank you.

Top K Frequent Elements - Leetcode

Comments

More from this blog

Atomic Habits

Mongo DB Basics

MongoDB Data-Types

Persevering Through Trials and Tribulations as a Developer: Dev Retro 2022

Shiny Object Syndrome in Tech

Command Palette

Comments

More from this blog