L347. Top K Frequent Elements

Problem:

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.

Solution:

• n size with MaxHeap

class Element{
    int val;
    int frequency;
    public Element(int val, int frequency){
        this.val = val;
        this.frequency = frequency;
    }
}

public List<Integer> topKFrequent(int[] nums, int k){
    List<Integer> res = new ArrayList<>();
    if(nums == null) return res;
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int count = map.get(nums[i]);
        count++;
        map.put(nums[i], count);
    }else{
        map.put(nums[i], 1);
    }
    PriorityQueue<Element> maxHeap = new PriorityQueue(nums.length, new Comparator<Element>(){
        @Override
        public int compare(Element e1, Element e2){
            return e2.frequency - e1.frequency;
        }
    })
    for(int key : map.keySet()){
        maxHeap.offer(new Element(key, map.get(key)));
    }
    while(k--> 0){
        res.add(maxHeap.poll().val)
    }
    return res;
}

• k size with MinHeap

class Element{
    int val;
    int frequency;
    public Element(int val, int frequency){
        this.val = val;
        this.frequency = frequency;
    }
}
              
public List<Integer> topKFrequent(int[] nums, int k){
    List<Integer> res = new ArrayList<Integer>();
    if(nums == null) return res;
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int i = 0 ; i < nums.length; i++ ){
        if(map.containsKey(nums[i])){
            int count = map.get(nums[i]);
            count++;
            map.put(nums[i], count);
        }else{
            map.put(nums[i], 1);
        }
    }  
            
    PriorityQueue<Element> minHeap = new PriorityQueue(nums.length, new Comparator<Element>(){
        @Override
        public int compare(Element e1, Element e2){
            return e1.frequency - e2.frequency;
        }
    });
            
            
    for(int key: map.keySet()){
        if(minHeap.size() < k){
            minHeap.offer(new Element(key, map.get(key)));
        }else if(map.get(key) > minHeap.peek().frequency){
            minHeap.poll();
            minHeap.offer(new Element(key, map.get(key)));
        }
    }
    while(minHeap.size() != 0){
        res.add(0, minHeap.poll().val);
    }
    return res;   
}