class Pair
{
    int num;
    int freq;
    Pair(int freq, int num)
    {
        this.num = num;
        this.freq = freq;
    }

    public int getFreq()
    {
        return this.freq;
    }

    public int getNumber()
    {
        return this.num;
    }
}

class Solution {
    /**
    1. Define hashmap to store frequencies of each number present in given array
    2. Since we need to store keys according to highest frequency, sort the map in descending order
    3. convert the map into List<Map>
    4. sort according to frequencies stored in map
    5. convert the sorted list into sorted hashmap by iterating over the sorted list and store ky,value pair in sorted map
    6. iterate over the sorted map and find the top-k frequent elements and store them in array
    7. return that resultant array
    */
    // O(n log n) O(n)
    public int[] topKFrequent(int[] nums, int k) {
        // map : <element, frequency>
        Map<Integer, Integer> map = new HashMap<>();
        for(int ele : nums)
        {
            map.put(ele, map.getOrDefault(ele, 0) + 1);
        }

        // sort the map according to frequencies in desc order
        // so convert map into list and then sort list
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort( (a,b) -> b.getValue().compareTo(a.getValue()));

        // convert the sorted list into sorted map
        Map<Integer, Integer> sortedMap = new LinkedHashMap<>();
        for(Map.Entry<Integer, Integer> entry : list)
        {
            int key = entry.getKey();
            int freq = entry.getValue();

            sortedMap.put(key, freq);
        }

        // fetch the topmost k-keys from sorted map
        int index=0,count=0;
        int[] arr = new int[k];
        for(Map.Entry<Integer,Integer> entry : sortedMap.entrySet())
        {
            arr[index] = entry.getKey();
            index++;
            count++;
            if(count == k)
                break;
        }
        return arr;
    }
    
    
    /**
    1. Define hashmap to store frequencies of each number present in given array
    2. Define a min heap that will store <frequency, number> in ascending order
    3. Iterate over a hashmap and insert the pair of <frequency, number> into min-heap
    4. if anytime min-heap size becomes greater than K, pop out elements from heap
    5. Convert the elements stored in min-heap to arraylist and then to array 'res'
    6. return res array.
    */
    // O(n log k) O(n)
    public int[] topKFrequent(int[] nums, int k) {
        // map : <element, frequency>
        Map<Integer, Integer> map = new HashMap<>();
        for(int ele : nums)
        {
            map.put(ele, map.getOrDefault(ele, 0) + 1);
        }

        // Min heap to keep top k elements
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.getFreq() - b.getFreq());
        for(Map.Entry<Integer, Integer> entry : map.entrySet())
        {
            int freq = entry.getValue();
            int key = entry.getKey();
            pq.offer(new Pair(freq, key));

            // remove least frequent element
            if(pq.size() > k)
                pq.poll();
        }

        ArrayList<Integer> list = new ArrayList<>();
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int ele = pair.num;
            list.add(ele);
        }

        int[] res = new int[list.size()];
        int l = 0;
        for(int ele : list)
        {
            res[l] = ele;
            l++;
        }    
        return res;
        OR
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}