Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
  • It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
  • You can return the answer in any order.
Approach 1: Create a FrequencyMap and Sort by values.
  1. Create a HashMap out of the array. Where the key of the Map is the element from nums and the value is the frequency of each number. This step takes O(N) time where N is the number of elements in the list.
  2. Once the Map is constructed from the array, then We can sort the HashMap by values to get the desired result. This step will take O(NlogN)
  3. If we create the frequency map for the given input and sort it by values:
    • Key Value 1 3 2 2 3 1

Following is the Java Implementation:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class MapComparator implements Comparator<Map.Entry<Integer, Integer>> {
    public int compare(Map.Entry<Integer, Integer> entry1,
                       Map.Entry<Integer, Integer> entry2) {
        return (entry2.getValue() - entry1.getValue());
    }
}

class TopKFrequent {
    public List<Integer> getTopK(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            int count = frequencyMap.getOrDefault(num, 0);
            frequencyMap.put(num, (count + 1));
        }
        List<Map.Entry<Integer, Integer>> entryList =
                new ArrayList<>(frequencyMap.entrySet());
        Collections.sort(entryList, new MapComparator());
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : entryList) {
            if (k > 0) {
                result.add(entry.getKey());
                k--;
            } else break;
        }
        return result;
    }
}

public class Solution {
    public static void main(String[] args) {
        TopKFrequent topKFrequent = new TopKFrequent();
        int k = 2;
        int[] nums = {4, 1, -1, 2, -1, 2, 3};
        List<Integer> result = topKFrequent.getTopK(nums, k);
        System.out.println(result);
    }
}
Approach 2: Create a FrequencyMap and MinHeap to track top k elements
  1. Create a HashMap out of the array. Where the key of the Map is the element from nums and the value is the frequency of each number. This step takes O(N) time where N is the number of elements in the list.
  2. The second step is to build a heap. The time complexity of adding an element in a heap is O(log(k)) and we do it N times that means O(Nlog(k)) time complexity for this step. The last step to build an output list.
class Element{
    int num;
    int count;
    
    public Element(int n, int c){
        this.num = n;
        this.count = c;
    }
}


class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        
        Map<Integer, Integer> countMap = new HashMap<>();
        for(int n : nums){
            int frequency = countMap.getOrDefault(n, 0);
            countMap.put(n, frequency+1);
        }
        
        Queue<Element> minHeap = new PriorityQueue<>(new Comparator<Element>(){
            
            public int compare(Element e1, Element e2){
                return Integer.compare(e1.count, e2.count);
            }
        });
        
        for(int key : countMap.keySet()){
            Element element = new Element(key, countMap.get(key));
            minHeap.offer(element);
            if(minHeap.size() > k){
                minHeap.poll();
            }
        }
        
        int i = 0;
        int[] result = new int[k];
        for(Element elem : minHeap){
            result[i] = elem.num;
            i++;
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(Nlog(k)). The complexity of the Counter method is O(N). To build a heap and output list takes O(Nlog(k)). Hence the overall complexity of the algorithm is O(N+Nlog(k))=O(Nlog(k)).
  • Space Complexity: O(N) to store the hash map.

Categories: Heap

Tagged as:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s