GeeksforGeeks Problem Of The Day POTD Solutions | 5 November 23 - Coding

Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Heaps but will also help you build up problem-solving skills.

POTD Solutions 5 Nov’ 2023

POTD 05 November: Top K Frequent Elements in Array

Given a non-empty array nums[] of integers of length N, find the top k elements which have the highest frequency in the array. If two numbers have same frequencies, then the larger number should be given more preference.

Example:

Input: N = 6, nums = {1,1,1,2,2,3}, k = 2
Output: {1, 2}
Explanation: The most frequent element in nums[] is 1 and the second most frequent element is 2.

Input: N = 8, nums = {1,1,2,2,3,3,3,4}, k = 2
Output: {3, 2}
Explanation: Element 3 is the most frequent. Elements 1 and 2 have the same frequency ie. 2. Therefore, in this case, the answer includes the element 2 as 2 > 1.

Find K most occurring elements in the given Array using Max-Heap:

Create a Map to store element-frequency pair. Map is used to perform insertion and updates in constant time. Then use a priority queue to store the element-frequency pair (Max-Heap). The element which has maximum frequency, comes at the root of the Priority Queue. Remove the top or root of Priority Queue K times and print the element.

Steps-by-step approach:

Create a map mp, to store key-value pair, i.e. element-frequency pair.
Traverse the array from start to end.
For every element in the array update mp[array[i]]++
Store the element-frequency pair in a Priority Queue
Run a loop k times, and in each iteration remove the root of the priority queue and print the element.

Below is the implementation of the above approach:

C++

class Solution { 
public: 
    // Comparison function defined for the priority queue 
    struct compare { 
        bool operator()(pair<int, int> p1, 
                        pair<int, int> p2) 
        { 
            // If frequencies of two elements are same 
            // then the larger number should come first 
            if (p1.second == p2.second) 
                return p1.first < p2.first; 
  
            // Insert elements in the priority queue on the 
            // basis of decreasing order of frequencies 
            return p1.second < p2.second; 
        } 
    }; 
    vector<int> topK(vector<int>& nums, int k) 
    { 
        // unordered_map 'mp' implemented as frequency hash 
        // table 
        int n = nums.size(); 
        vector<int> ans; 
        unordered_map<int, int> mp; 
        for (int i = 0; i < n; i++) 
            mp[nums[i]]++; 
  
        // priority queue 'pq' implemented as max heap on 
        // the basis of the comparison operator 'compare' 
        // element with the highest frequency is the root of 
        // 'pq' in case of conflicts, larger element is the 
        // root 
        priority_queue<pair<int, int>, 
                       vector<pair<int, int> >, compare> 
            pq(mp.begin(), mp.end()); 
  
        // Store the top k most frequent element 
        for (int i = 1; i <= k; i++) { 
            ans.push_back(pq.top().first); 
            pq.pop(); 
        } 
        return ans; 
    } 
};

Java

class Solution { 
    public int[] topK(int[] nums, int k) 
    { 
        int n = nums.length; 
        int ans[] = new int[k]; 
        Map<Integer, Integer> mp 
            = new HashMap<Integer, Integer>(); 
  
        // Put count of all the 
        // distinct elements in Map 
        // with element as the key & 
        // count as the value. 
        for (int i = 0; i < n; i++) { 
  
            // Get the count for the 
            // element if already 
            // present in the Map or 
            // get the default value 
            // which is 0. 
            mp.put(nums[i], 
                   mp.getOrDefault(nums[i], 0) + 1); 
        } 
  
        // Create a Priority Queue 
        // to sort based on the 
        // count or on the key if the 
        // count is same 
        PriorityQueue<Map.Entry<Integer, Integer> > queue 
            = new PriorityQueue<>( 
                (a, b) 
                    -> a.getValue().equals(b.getValue()) 
                           ? Integer.compare(b.getKey(), 
                                             a.getKey()) 
                           : Integer.compare(b.getValue(), 
                                             a.getValue())); 
  
        // Insert the data from the map 
        // to the Priority Queue. 
        for (Map.Entry<Integer, Integer> entry : 
             mp.entrySet()) 
            queue.offer(entry); 
  
        // // Store the top k most frequent elemen 
        for (int i = 0; i < k; i++) { 
            ans[i] = queue.poll().getKey(); 
        } 
        return ans; 
    } 
}

Python3

import heapq 
  
  
class Solution: 
    def topK(self, nums, k): 
  
        mp = dict() 
        ans = [0] * k 
        n = len(nums) 
  
        # Put count of all the distinct elements 
        # in dictionary with element as the 
        # key & count as the value. 
        for i in range(0, n): 
            if nums[i] not in mp: 
                mp[nums[i]] = 0
            else: 
                mp[nums[i]] += 1
  
        # Using heapq data structure 
        heap = [(value, key) for key, 
                value in mp.items()] 
  
        # Get the top k elements 
        largest = heapq.nlargest(k, heap) 
  
        # Insert the data from the map to 
        # the priority queue 
  
        # Store the top K most frequent elemen 
        for i in range(k): 
            ans[i] = largest[i][1] 
  
        return ans 

Javascript

class Solution { 
    topK(nums, k) { 
        let mp = new Map(); 
        // Put count of all the 
        // distinct elements in Map 
        // with element as the key & 
        // count as the value. 
          
        let ans = new Array(k); 
        let n = nums.length; 
          
        for (let i = 0; i < n; i++) { 
    
            // Get the count for the 
            // element if already 
            // present in the Map or 
            // get the default value 
            // which is 0. 
            if(!mp.has(nums[i])) 
                mp.set(nums[i],0); 
               
            mp.set(nums[i], 
                   mp.get(nums[i]) + 1); 
        } 
    
        // Create a Priority Queue 
        // to sort based on the 
        // count or on the key if the 
        // count is same 
        let queue=[...mp]; 
           
        queue.sort(function(a,b){ 
            if(a[1]==b[1]) 
            { 
                return b[0]-a[0]; 
            } 
            else
            { 
                return b[1]-a[1]; 
            } 
        }); 
          
        for(let i=0; i<k; i++) 
        { 
            ans[i] = queue[i][0]; 
        } 
        return ans; 
    } 
}

Time Complexity: O(K log D + D log D), where D is the count of distinct elements in the array.
Auxiliary Space: O(D), where D is the count of distinct elements in the array.

Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Dynamic Programming in Game Theory for Competitive Programming
GeeksforGeeks Problem Of The Day POTD Solutions \| 4 November 23
GeeksforGeeks Problem Of The Day POTD Solutions \| 3 November 23
DP on Trees for Competitive Programming
GeeksforGeeks Problem Of The Day POTD Solutions \| 1 November 23

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12