{"id":775,"date":"2023-12-06T20:00:00","date_gmt":"2023-12-06T20:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=775"},"modified":"2023-12-08T13:06:44","modified_gmt":"2023-12-08T13:06:44","slug":"top-k-frequent-elements","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/top-k-frequent-elements\/","title":{"rendered":"Find Top K Frequent Elements in an Array (with code)"},"content":{"rendered":"\n<p>In many programming situations, finding the top k most occurring elements in an array is a common task. This is a problem encountered in various scenarios in a dataset for decision-making. In this article, we&#8217;ll explore solutions to the Top K Frequent Elements problem using C++, Java, and Python.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Top K Frequent Elements Problem?<\/strong><\/h2>\n\n\n\n<p>In this problem, we have to find the K most frequent elements in an array.<strong> In other words, given an array of integers, the task is to identify the K elements that occur most frequently in the array.<\/strong><\/p>\n\n\n\n<p>Let us understand it with an example:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\">Array = [1,1,1,2,2,3,4]<br>K = 2<br>Output = [1,2]<\/p>\n\n\n\n<p>Element 1 appears 3 times and 2 appears 2 times, these both are the most occurring elements:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"233\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-3-1024x233.png\" alt=\"Example of top k frequent elements\" class=\"wp-image-779\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-3-1024x233.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-3-300x68.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-3-768x175.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-3-750x171.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-3-1140x259.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-3.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\"><strong>Hashmap Approach to Solve It<\/strong><\/h2>\n\n\n\n<p><strong>In the Hashmap approach, we will use a hashmap to store the frequency of each element present in the array, so that we can count the occurrence of each element.<\/strong><\/p>\n\n\n\n<p>Steps to solve the problem using this approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Firstly we will declare an unordered map to store the frequency of all elements present in the array and run a loop to count the occurrence of each element.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"434\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-3-1024x434.png\" alt=\"unordered map to store the frequency\" class=\"wp-image-780\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-3-1024x434.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-3-300x127.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-3-768x325.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-3-750x318.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-3-1140x483.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-3.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will convert the hashmap into a vector of pairs for easier sorting using a <a href=\"https:\/\/favtutor.com\/blogs\/sort-vector-cpp\">custom comparator<\/a>.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"181\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-3-1024x181.png\" alt=\"convert the hashmap into a vector\" class=\"wp-image-781\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-3-1024x181.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-3-300x53.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-3-768x136.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-3-750x132.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-3-1140x201.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-3.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will Sort the vector of pairs based on the second element in descending order<\/li>\n\n\n\n<li>Now we will Extract the top k frequent elements using a loop on the vector of pairs and iterating it for k times. And push it into our vector.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Below is the C++ program to find the Top K Frequent Elements in an Array using Hashmap approach:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\n\/\/ Function to compare pairs based on the second element (frequency)\nstatic bool cmp(const pair&lt;int, int&gt;&amp; a, const pair&lt;int, int&gt;&amp; b) {\n    return a.second &gt; b.second;\n}\n\n\/\/ Function to find the top k frequent elements in the array\nvector&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) {\n    \/\/ Vector to store the result\n    vector&lt;int&gt; ans;\n    \n    \/\/ Hash map to store the frequency of each number in the array\n    unordered_map&lt;int, int&gt; mp;\n\n    \/\/ Step 1: Count the frequency of each number in the array\n    for (int i = 0; i &lt; nums.size(); i++) {\n        mp[nums[i]]++;\n    }\n\n    \/\/ Convert the hash map to a vector of pairs for easier sorting\n    vector&lt;pair&lt;int, int&gt;&gt; freqVec(mp.begin(), mp.end());\n\n    \/\/ Step 2: Sort the vector of pairs based on the second element (frequency)\n    sort(freqVec.begin(), freqVec.end(), cmp);\n\n    \/\/ Step 3: Extract the top k frequent elements\n    for (int i = 0; i &lt; k; i++) {\n        ans.push_back(freqVec[i].first);\n    }\n\n    \/\/ Return the result vector\n    return ans;\n}\n\n\/\/ Main function\nint main() {\n    \/\/ Input array and value of k\n    vector&lt;int&gt; nums = {1, 1, 1, 2, 2, 3, 4};\n    int k = 2;\n\n    \/\/ Call the function to find the top k frequent elements\n    vector&lt;int&gt; result = topKFrequent(nums, k);\n\n    \/\/ Print the result\n    cout &lt;&lt; &quot;Top &quot; &lt;&lt; k &lt;&lt; &quot; frequent elements: &quot;;\n    for (int num : result) {\n        cout &lt;&lt; num &lt;&lt; &quot; &quot;;\n    }\n\n    \/\/ Return 0 to indicate successful completion\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>We can also implement it in Java as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.*;\n\npublic class TopKFrequentElements {\n\n    \/\/ Function to compare pairs based on the second element (frequency)\n    static class PairComparator implements Comparator&lt;Map.Entry&lt;Integer, Integer&gt;&gt; {\n        public int compare(Map.Entry&lt;Integer, Integer&gt; a, Map.Entry&lt;Integer, Integer&gt; b) {\n            return b.getValue().compareTo(a.getValue());\n        }\n    }\n\n    \/\/ Function to find the top k frequent elements in the array\n    public static int[] topKFrequent(int[] nums, int k) {\n        \/\/ Map to store the frequency of each number in the array\n        Map&lt;Integer, Integer&gt; frequencyMap = new HashMap&lt;&gt;();\n\n        \/\/ Step 1: Count the frequency of each number in the array\n        for (int num : nums) {\n            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);\n        }\n\n        \/\/ Convert the map to a list of entries for easier sorting\n        List&lt;Map.Entry&lt;Integer, Integer&gt;&gt; freqList = new ArrayList&lt;&gt;(frequencyMap.entrySet());\n\n        \/\/ Step 2: Sort the list of entries based on the second element (frequency)\n        freqList.sort(new PairComparator());\n\n        \/\/ Step 3: Extract the top k frequent elements\n        int[] result = new int[k];\n        for (int i = 0; i &lt; k; i++) {\n            result[i] = freqList.get(i).getKey();\n        }\n\n        \/\/ Return the result array\n        return result;\n    }\n\n    \/\/ Main function\n    public static void main(String[] args) {\n        \/\/ Input array and value of k\n        int[] nums = {1, 1, 1, 2, 2, 3, 4};\n        int k = 2;\n\n        \/\/ Call the function to find the top k frequent elements\n        int[] result = topKFrequent(nums, k);\n\n        \/\/ Print the result\n        System.out.print(&quot;Top &quot; + k + &quot; frequent elements: &quot;);\n        for (int num : result) {\n            System.out.print(num + &quot; &quot;);\n        }\n    }\n}\n<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>The Hashmap approach can be implemented with Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">from typing import List\nfrom collections import Counter\n\n# Function to find the top k frequent elements in the array\ndef top_k_frequent(nums: List[int], k: int) -&gt; List[int]:\n    # Step 1: Count the frequency of each number in the array\n    freq_map = Counter(nums)\n\n    # Step 2: Convert the Counter to a list of tuples for easier sorting\n    freq_list = list(freq_map.items())\n\n    # Step 3: Sort the list of tuples based on the second element (frequency)\n    freq_list.sort(key=lambda x: x[1], reverse=True)\n\n    # Step 4: Extract the top k frequent elements\n    result = [num for num, freq in freq_list[:k]]\n\n    # Return the result list\n    return result\n\n# Main function\nif __name__ == &quot;__main__&quot;:\n    # Input array and value of k\n    nums = [1, 1, 1, 2, 2, 3, 4]\n    k = 2\n\n    # Call the function to find the top k frequent elements\n    result = top_k_frequent(nums, k)\n\n    # Print the result\n    print(&quot;Top&quot;, k, &quot;frequent elements:&quot;, result)<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>Top 2 frequent elements: &#91;1, 2]<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Complexity Analysis<\/strong><\/h3>\n\n\n\n<p>The time complexity is O(n + M * log(M) + k) due to iterating through the array (n), sorting the frequency vector (M * log(M)), and extracting the top k elements<\/p>\n\n\n\n<p>The space complexity is O(M) for the frequency map we have used in our approach where M is the number of unique elements in the array<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, the <a href=\"https:\/\/leetcode.com\/problems\/top-k-frequent-elements\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> of finding the top k frequent elements in an array can be efficiently solved using a hashmap approach. By counting the frequency of each element, converting the hashmap into a vector of pairs, and sorting based on frequency, we can easily extract the top k frequent elements. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here is the solution to the leetcode problem to find top k frequent elements in an array using hashmap approach.<\/p>\n","protected":false},"author":12,"featured_media":848,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-775","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/775","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=775"}],"version-history":[{"count":6,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/775\/revisions"}],"predecessor-version":[{"id":871,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/775\/revisions\/871"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/848"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=775"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=775"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=775"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}