Top K Frequent Elements

In this approach, we are going to loop through numbers in nums array and store the number as key to its count of how many times that number have appeared as value into a HashMap.

Then, copy the entries of HashMap into a List and sort them by the count of how many times that it appeared. i.e. using entry's value. (The reason we are copying into a List is because, we want to use Java's inbuilt sorting utility functions).

After the entries are sorted, take the last k elements from sorted list.

Consider an example with nums[1, 1, 1, 2, 3, 2, 1] and k = 2, so we need to find top 2 frequent elements.

• In the first step, we will initialize a HashMap and store the count of each number to number of times it appeared.
  Java

  HashMap<Integer, Integer> map = new HashMap<>();
  IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));

  Now, the HashMap will looks like this. 1 appeared 4 times, 2 appeared 2 times and 3 appeared 1 time.

  Mapping

  key	value
  1	4
  2	2
  3	1

• Now, take these entries into a ArrayList and sort them by count of the number.
  Code

  ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
    list.sort(Comparator.comparingInt(Map.Entry::getValue));

  After sorting, it looks like this.

  List after sorting

  entry key	entry value
  3	1
  2	2
  1	4

• Now, we will return the last two eleemnts from this sorted list. i.e. [2, 1] or [1, 2] in any order.

import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;

public class TopKFrequentElements {


    /**
      *  First, store the mapping of number -> number of times it appeared into a HashMap
      *  Second, sort the entries of HashMap using the values (number of times a number is appeared)
      *  Then, take last K elements
      */
    static int[] usingSorting(int[] nums, int k) {
        int[] ans = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Comparator.comparingInt(Map.Entry::getValue));
        for(int i=0; i<k; i++) {
            ans[i] = list.get(list.size()-1-i).getKey();
        }
        return ans;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n log(n)) time where n is the input array nums length.
Space complexity: O(n).

In this approach, we are going to loop through numbers in nums array and store the number as key to its count of how many times that number appeared as value into a HashMap.

In the next step we are going to create a PriorityQueue (Heap data structure in Java with default implementation of min heap, meaning that parent node will always have min value than its children).

Then in the next step, we will loop through HashMap entries and then add to the PriorityQueue, while doing that keep checking if PriorityQueue size is exceeding size k, whenever it exceeds size k remove elements from PriorityQueue so that it only keeps top k elements only.

Finally return the elements from the PriorityQueue.

Consider an example with nums[1, 1, 1, 2, 3, 2, 1] and k = 2, so we need to find top 2 frequent elements.

• In the first step, we will initialize a HashMap and store the count of each number to number of times it appeared.
  Java

  HashMap<Integer, Integer> map = new HashMap<>();
  IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));

  Now, the HashMap will looks like this. 1 appeared 4 times, 2 appeared 2 times and 3 appeared 1 time.

  Mapping

  key	value
  1	4
  2	2
  3	1

• Now we will initialize PriorityQueue which will use HashMap entry's value when it needs to orders elements inside Heap.
  Java

  PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k, Comparator.comparingInt(Map.Entry::getValue));

• Now, then loop through HashMap entries, add them to the PriorityQueue we created above and whenever it reaches k+1 size then remove the top element, so that it keeps only k elements.
  Code

  map.entrySet().forEach(entry->{
    minHeap.offer(entry);
    if(minHeap.size() >k) {
        minHeap.poll();
    }
  });

  At the end PriorityQueue, it looks like this.

  List after sorting

  entry key	entry value
  1	4
  2	2

• Now, we will return the eleemnts from this PriorityQueue, which will be [1, 2]

import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;

public class TopKFrequentElements {

    /**
      *
      * First, store the mapping of number -> number of times it appeared into a HashMap
      * Next, Crate a Min Heap (default Java Priority Queue is Min heap, i.e. at top it keeps min element and children are greater than parent)
      * Then, loop through entries of HashMap and add it to PriorityQueue, if it is reaches size 'k' then poll, by the end will  have top k elements
      */
    static int[] usingHeap(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
        final PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k, Comparator.comparingInt(Map.Entry::getValue));
        map.entrySet().forEach(entry->{
            minHeap.offer(entry);
            if(minHeap.size() >k) {
                minHeap.poll();
            }
        });
        int[] result = new int[k];
        for(int i=0;i<k; i++) {
            result[i] = minHeap.poll().getKey();
        }
        return result;
    }


}

Complexity Analysis:

Time complexity: Above code runs in O(n log(k)) time where n is the input array nums length and when PriorityQueue's heapify() function takes log k, since there will be at most k elements in the heap.
Space complexity: O(n).

In this approach, we are apply Quickselect algorithm (I have provided detailed explanation in Find Kth Largest Element problem's Solution 3).

We will be leveraging the same solution here. The main advantage with this solution is that, initially we will be selecting a random indexed element from the input array and call it pivot, then just like in quick sort algorithm, we will then move all elements smaller to the pivot to the left side of the pivot and all elements greater than pivot to the right side of the pivot, after this step pivot element is correctly positioned in the array if it is sorted.

Now we can draw a decision based on where pivot index is placed now:

• If k and pivot element's index are same, that means we have found our answer. All elements on the right side of pivot element are the top K frequent elements.
• If k is less than pivot element's index, that means we have left some elements on the left side of the array to cover top K frequent elements. Now, we update our scope of algorithm to 0th index to pivot's index.
• If k is greater than pivot element's index, that means we have extra elements on the right side of the array to cover top K frequent elements. Now, we update our scope of algorithm to pivot's index right index.

This algorithm runs with average time complexity of O(n) in average case, but worst case time complexity of O(n2).

import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;

public class TopKFrequentElements {

    /**
      * Using QuickSelect algorithm
      */
    static int[] usingQuickSelect(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
        Map.Entry<Integer, Integer>[] entries= map.entrySet().toArray(new Map.Entry[0]);
        // we are passing k as entries.length - k, because we need last k elements
        selectTopKFrequent(entries, 0, entries.length-1, entries.length-k); //entries wil be updated by reference
        int[] result = new int[k];
        for(int i=0; i<k; i++) { // take last k elements from array
            result[i] = entries[entries.length-1-i].getKey();
        }
        return result;
    }

    static void selectTopKFrequent(Map.Entry<Integer, Integer>[] entries, int left, int right, int k) {
        if(left == right) {
            return;
        }

        int storeIndex = partition(entries, left, right);

        if(storeIndex == k) {
            //k is positioned at the right place
            return;
        } else if (k< storeIndex) { // if K is smaller than current pivot, move to the left
            selectTopKFrequent(entries, left, storeIndex -1, k);
        } else {
            selectTopKFrequent(entries, storeIndex+1, right, k);
        }
    }

    static int partition(Map.Entry<Integer, Integer>[] entries, int left, int right) {

        Map.Entry<Integer, Integer> pivotIndexElement = entries[right]; //we are choosing right index to be pivot index, but we can select any random one
        int storeIndex = left;
        for(int i=left;i<right; i++) {
            if(entries[i].getValue() < pivotIndexElement.getValue()) {
                // swap these entries
                swap(entries, i, storeIndex);
                storeIndex++;
            }
        }
        swap(entries, right, storeIndex); // move pivot to its final place, meaning that,
                                            // left side elements are now smaller than pivot and right elements
                                            // are greater than pivot
        return storeIndex;
    }

    // utility to swap i, j indexed elements
    static void swap(Map.Entry<Integer, Integer>[] entries, int i, int j) {
        Map.Entry<Integer, Integer> temp = entries[i];
        entries[i] = entries[j];
        entries[j] = temp;
    }


}

Complexity Analysis:

Time complexity: Above code runs in O(n) time in average case, but takes O(n²) in worst case where n is the input array nums length. heapify() function takes log k, since there will be at most k elements in the heap.
Space complexity: O(n) for storing elements count into HashMap.

In this approach we will be using a technique from Bucket Sort, but we will not be sorting the array, so we will not be discussing details of bucket sorting here.

Similar to all above approaches, we will first go through array and count how many times an element appeared and store this information into a HashMap.

Next, we will create an array with the same size as input array, each element in the array will be a bucket (we will use an ArrayList). Then, we will go through entries of HashMap and store elements into array buckets into the index whose value will be same as the number of times it appeared. (No element in array will appear more than the times of input array length, this is the key to this solution).

For example, say nums = [1, 1, 1, 3, 2, 2, 4, 1] and k =2, in the input array 1 appeared 4 times, 2 appeared 2 times, 3 appeared 1 time and 4 appeared 1 time.

Now, when we place these into buckets array, this is how it will look like. (we have created n+1 buckets to map exactly n count to n^th index).

buckets = [null, [3, 4], [2], null, [1], null, null, null, null]

Now, we can loop this buckets array from right to left and just take k elements.

import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;

public class TopKFrequentElements {


    /**
      * 
      * Using a temporary array to store elements into respective indexes based the number of times they have appeared.
      */
    static int[] usingBucketSortingTechnique(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));

        // Now, we will create n buckets to store count of number of times an element appeared
        // index of array is the number of times an element appeared, within that bucket we will store elements
        // that have appeared same number of times

        List<Integer>[] buckets = new List[nums.length+1];// added +1 to keep n times appeared element into n(th) index
        map.forEach((key, value) -> {
            if (buckets[value] == null) {
                buckets[value] = new ArrayList<>();
            }
            buckets[value].add(key);
        });

        int[] result = new int[k];
        for(int i= buckets.length-1; i>=0 && k>0 ; i--) {
            if(buckets[i] != null) {
                List<Integer> elements = buckets[i];
                for(int j=0; j<elements.size() && k>0; j++) {
                    result[k-1] = elements.get(j);
                    k--;
                }
            }
        }
        return result;
    }


}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(n) for storing elements count into HashMap.