{"id":9304,"date":"2022-08-25T11:40:52","date_gmt":"2022-08-25T11:40:52","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9304"},"modified":"2022-09-13T12:58:15","modified_gmt":"2022-09-13T12:58:15","slug":"next-greater-frequency-element","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/","title":{"rendered":"Next Greater Frequency Element"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg\" alt=\"\" \/><\/p>\n<h3>Problem statement<\/h3>\n<p>Given an array, consisting of n elements, find the next greater frequency element of each element. The next greater frequency element of any element is the first element to its right having a greater frequency than its own frequency.<\/p>\n<p><strong>Input<\/strong>: Integer array of size of n.<br \/>\n<strong>Output<\/strong>: Integer array of size n.<\/p>\n<p><strong>Test cases<\/strong>:<br \/>\n<strong>Input<\/strong>:<br \/>\n[1, 4, 2, 4, 2, 3, 2]<\/p>\n<p><strong>Output<\/strong>:<br \/>\n[4, 2, -1, 2, -1, 2, -1]<\/p>\n<h4>Explanation:<\/h4>\n<p>Frequency of 1 -&gt; 1<br \/>\nFrequency of 2 -&gt; 3<br \/>\nFrequency of 4 -&gt; 2<br \/>\nFrequency of 3 -&gt; 1<\/p>\n<ul>\n<li>Output[0] = 4 because next to 1 there is 4 and frequency of 4 is greater than 1.<\/li>\n<li>Output[1] = 2 because next to 4 there is 2 and frequency of 2 is greater than 4.<\/li>\n<li>Output[2] = -1 because 2 does not have any lament to its right having a frequency greater than its own.<\/li>\n<li>Output[3] = 2 because next to 4 there is 2 and frequency of 2 is greater than 4.<\/li>\n<li>Output[4] = -1 because 2 does not have any lament to its right having a frequency greater than its own.<\/li>\n<li>Output[5] = 2 because next to 3 there is 2 and frequency of 2 is greater than 3.<\/li>\n<li>Output[6] = -1 because 2 does not have any element to its right.<\/li>\n<\/ul>\n<h3>Naive Approach &#8211; Brute Force<\/h3>\n<p>The idea is to use a hashing. The <a href=\"https:\/\/prepbytes.com\/blog\/java\/treemap-vs-hashmap-vs-linkedhashmap-in-java\/\" title=\"hashmap\">hashmap<\/a> will be used to store key-value pairs, where key will be any element of the array and the value be the frequency of that element.<br \/>\nAfter creating the required hashmap, we will iterate each element of the given array and for each element we will check all the elements to its right.<br \/>\nIf after checking all the elements to the right we still do not find the next greater frequency element, then the answer for that element will be -1, otherwise the answer for that element will be the first element we find with a greater frequency than it.<\/p>\n<h4>Algorithm<\/h4>\n<pre><code>1. Initialize an empty stack and an array.\n2. Calculate frequency of each element and store it in the map.\n3. For each i in 0 to n:\n    a. For each j in i + 1 to n\n        i. If frequency of arr[j] > frequency of arr[i], \n        then ans[i] = arr[j]\n    b. If we does not found the next greater frequency\n    element, then ans[i] = -1\n4. Return ans array.<\/code><\/pre>\n<h3>Code Implementation:<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_9303 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_9303 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_9303 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_9303 .wpsm_nav-tabs > li.active > a, #tab_container_9303 .wpsm_nav-tabs > li.active > a:hover, #tab_container_9303 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_9303 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_9303 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_9303 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_9303 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_9303 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_9303 .wpsm_nav-tabs > li > a:hover , #tab_container_9303 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_9303 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_9303 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_9303 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_9303 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_9303 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_9303 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_9303 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_9303 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_9303 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_9303 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_9303 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_9303\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_9303\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_9303_1\" aria-controls=\"tabs_desc_9303_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_9303\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_9303_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nimport java.util.HashMap;\r\nclass Prepbytes {\r\n\r\n    \/\/ This function will find the next greater frequency element for each \r\n    \/\/ element\r\n    public static int[] nextGFE(int arr[], int n)\r\n    {\r\n          HashMap&lt;Integer, Integer&gt; map = new HashMap&lt;&gt;();\r\n\t    int ans[] = new int[n];\r\n\r\n\t    for(int e : arr){\r\n\t        map.put(e, map.getOrDefault(e, 0)+1);\r\n\t    }\r\n\t    \r\n\t    for(int i = 0; i &lt; n; i++){\r\n\t        boolean found = false;\r\n\t        for(int j = i+ 1; j&lt; n;j++){\r\n\t            if(map.get(arr[j])&gt;map.get(arr[i])){\r\n\t                ans[i] = arr[j];\r\n\t                found = true;\r\n\t                break;\r\n\t            }\r\n\t        }\r\n\t        if(!found){\r\n\t            ans[i] = -1;\r\n\t        }\r\n\t    }\r\n\t    return ans;\r\n    }\r\n    \r\n    public static void main(String[] args) {\r\n        int arr[] = new int[]{1, 4, 2, 4, 2, 3, 2};\r\n        int ans[] = nextGFE(arr, arr.length);\r\n        for(int e : ans){\r\n            System.out.print(e+&quot; &quot;);\r\n        }\r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_9303 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_9303 a\"),jQuery(\"#tab-content_9303\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Output<\/strong>:<br \/>\n4 2 -1 2 -1 2 -1<\/p>\n<p><strong>Time complexity<\/strong>: O(n^2). It takes O(n) to find the next greater frequency element of one element, and we have to find n elements. Hence, the time complexity will be O(n^2)<\/p>\n<p><strong>Space Complexity<\/strong>: O(n). The space required is only for the input and output array. The auxiliary space complexity is O(1).<\/p>\n<h3>Efficient Approach &#8211; Using Stack<\/h3>\n<p>The idea is to use hashing and stack. The hashmap will be used to store key-value pairs, where key will be any element of the array and the value be the frequency of that element.<br \/>\nThe stack will be used to store the element in a monotonically increasing order according to their frequencies. <\/p>\n<p>We will iterate every element in the given array. For each element, while the stack is not empty and the frequency of the current element is greater than the frequency of the top of the stack, we will keep removing the top of the stack. After the while loop terminates, there could be two possible cases:<\/p>\n<p><strong>Case 1<\/strong>: The stack is empty. If the stack is empty it means that there were no elements having a frequency greater than the current element. Hence, we will set ans[i] as -1.<\/p>\n<p><strong>Case 2<\/strong>: We found an element having a frequency greater than the current element. Then we will set ans[i] as the top of the stack.<\/p>\n<h4>Algorithm<\/h4>\n<pre><code>1. Initialize an empty stack, map and an array.\n2. Calculate frequency of each element and store it in the map.\n3. Iterate i from 0 to n.\n    a. While stack is not empty and the frequency of the current element\n    is greater than the frequency of the top of the stack\n        i. Remove the top the stack\n    b. If the stack is empty, then it mean there is \n    no next greater frequency element for this element\n        i. ans[i] =  -1.\n    c. Otherwise, ans[i] = top of the stack\n    d. Push the current element to the stack\n4. Return ans array.<\/code><\/pre>\n<h3>Code Implementation:<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_9308 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_9308 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_9308 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_9308 .wpsm_nav-tabs > li.active > a, #tab_container_9308 .wpsm_nav-tabs > li.active > a:hover, #tab_container_9308 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_9308 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_9308 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_9308 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_9308 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_9308 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_9308 .wpsm_nav-tabs > li > a:hover , #tab_container_9308 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_9308 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_9308 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_9308 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_9308 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_9308 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_9308 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_9308 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_9308 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_9308 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_9308 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_9308 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_9308\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_9308\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_9308_1\" aria-controls=\"tabs_desc_9308_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_9308\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_9308_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nimport java.util.Stack;\r\nimport java.util.HashMap;\r\nclass Prepbytes {\r\n\r\n    \/\/ This function will find the next greater frequency element for each \r\n    \/\/ element\r\n    public static int[] nextGFE(int arr[], int n)\r\n    {\r\n          \/\/ This map will store the element of the array as key \r\n          \/\/ and there frequency as value\r\n\t    HashMap&lt;Integer, Integer&gt; map = new HashMap&lt;&gt;();\r\n\t    Stack&lt;Integer&gt; st = new Stack&lt;&gt;();\r\n\t    int ans[] = new int[n];\r\n\r\n          \/\/ Calculate frequency of each element\r\n\t    for(int e : arr){\r\n\t        map.put(e, map.getOrDefault(e, 0)+1);\r\n\t    }\r\n\t    \r\n\t    \/\/ Iterate over the given array\r\n\t    for(int i = n - 1; i&gt;= 0; i--){\r\n\t        \r\n\t        \/\/ While stack is not empty and the frequency of the current\r\n\t        \/\/ element is greater than the frequency of the top of the\r\n\t        \/\/ stack, keeping removing the top of the stack\r\n\t        while(!st.isEmpty() &amp;&amp; map.get(arr[i]) &gt;= map.get(st.peek())){\r\n\t            st.pop();\r\n\t        }\r\n\t        \r\n\t        \/\/ If the stack is empty, then it mean there is no next greater\r\n\t        \/\/ frequency element for this element\r\n\t        if(st.isEmpty()){\r\n\t            ans[i] = -1;\r\n\t        } \r\n\t        \/\/ Otherwise, the top of the stack is the next greater\r\n\t        \/\/ frequency element for this element\r\n\t        else {\r\n\t            ans[i] = st.peek();\r\n\t        }\r\n\t        \r\n\t        \/\/ Push the current element to the stack\r\n\t        st.push(arr[i]);\r\n\t    }\r\n\t    return ans;\r\n    }\r\n    \r\n    public static void main(String[] args) {\r\n        int arr[] = new int[]{1, 4, 2, 4, 2, 3, 2};\r\n        int ans[] = nextGFE(arr, arr.length);\r\n        for(int e : ans){\r\n            System.out.print(e+&quot; &quot;);\r\n        }\r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_9308 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_9308 a\"),jQuery(\"#tab-content_9308\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Output<\/strong>:<br \/>\n4 2 -1 2 -1 2 -1<\/p>\n<p><strong>Time complexity<\/strong>: O(n). We can observe that every element is pushed and removed from the stack only once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we don\u2019t consider constant terms during asymptotic analysis of time complexity.<\/p>\n<p><strong>Space Complexity<\/strong>: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is O(n) as we are using a stack and a map. At any point of time the stack can contain at most n elements and the map can contain 2n elements.<\/p>\n<p>This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem. To practice more problems you can check out <a href=\"#\"><\/a> at <a href=\"https:\/\/www.prepbytes.com\/\"> Prepbytes<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem statement Given an array, consisting of n elements, find the next greater frequency element of each element. The next greater frequency element of any element is the first element to its right having a greater frequency than its own frequency. Input: Integer array of size of n. Output: Integer array of size n. Test [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[127],"tags":[],"class_list":["post-9304","post","type-post","status-publish","format-standard","hentry","category-stacks"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Next Greater Frequency Element | Stacks | PrepBytes Blog<\/title>\n<meta name=\"description\" content=\"This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Next Greater Frequency Element | Stacks | PrepBytes Blog\" \/>\n<meta property=\"og:description\" content=\"This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2022-08-25T11:40:52+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-09-13T12:58:15+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Next Greater Frequency Element\",\"datePublished\":\"2022-08-25T11:40:52+00:00\",\"dateModified\":\"2022-09-13T12:58:15+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/\"},\"wordCount\":668,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg\",\"articleSection\":[\"Stacks\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/\",\"name\":\"Next Greater Frequency Element | Stacks | PrepBytes Blog\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg\",\"datePublished\":\"2022-08-25T11:40:52+00:00\",\"dateModified\":\"2022-09-13T12:58:15+00:00\",\"description\":\"This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Stacks\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/stacks\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Next Greater Frequency Element\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Next Greater Frequency Element | Stacks | PrepBytes Blog","description":"This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/","og_locale":"en_US","og_type":"article","og_title":"Next Greater Frequency Element | Stacks | PrepBytes Blog","og_description":"This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem.","og_url":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2022-08-25T11:40:52+00:00","article_modified_time":"2022-09-13T12:58:15+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Next Greater Frequency Element","datePublished":"2022-08-25T11:40:52+00:00","dateModified":"2022-09-13T12:58:15+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/"},"wordCount":668,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg","articleSection":["Stacks"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/","url":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/","name":"Next Greater Frequency Element | Stacks | PrepBytes Blog","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg","datePublished":"2022-08-25T11:40:52+00:00","dateModified":"2022-09-13T12:58:15+00:00","description":"This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661420690920-Article%20%282%29.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/next-greater-frequency-element\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Stacks","item":"https:\/\/prepbytes.com\/blog\/category\/stacks\/"},{"@type":"ListItem","position":3,"name":"Next Greater Frequency Element"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/9304","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=9304"}],"version-history":[{"count":2,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/9304\/revisions"}],"predecessor-version":[{"id":9683,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/9304\/revisions\/9683"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=9304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=9304"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=9304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}