{"id":27284,"date":"2018-01-20T20:40:07","date_gmt":"2018-01-20T15:10:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27284"},"modified":"2018-01-20T20:40:07","modified_gmt":"2018-01-20T15:10:07","slug":"java-algorithm-next-greater-element","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-next-greater-element\/","title":{"rendered":"Java Algorithm &#8211; Next Greater Element"},"content":{"rendered":"<p>Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. <span id=\"more-8405\"><\/span>Elements for which no greater element exist, consider next greater element as -1.<\/p>\n<p>Examples:<br \/>\n<strong>a) <\/strong>For any array, rightmost element always has next greater element as -1.<br \/>\n<strong>b) <\/strong>For an array which is sorted in decreasing order, all elements have next greater element as -1.<br \/>\n<strong>c) <\/strong>For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.<\/p>\n<pre>Element       NGE\r\n   4      --&gt;   5\r\n   5      --&gt;   25\r\n   2      --&gt;   25\r\n   25     --&gt;   -1\r\n<\/pre>\n<p><strong>d)<\/strong> For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.<\/p>\n<pre>  Element        NGE\r\n   13      --&gt;    -1\r\n   7       --&gt;     12\r\n   6       --&gt;     12\r\n   12     --&gt;     -1<\/pre>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Method 1 (Simple)<\/strong><br \/>\nUse two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by outer loop. If a greater element is found then that element is printed as next, otherwise -1 is printed.<\/p>\n<p><strong>Java Programming:<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ Simple Java program to print next <br\/>\/\/ greater elements in a given array<br\/> <br\/>class Main<br\/>{ <br\/>    \/* prints element and NGE pair for <br\/>     all elements of arr[] of size n *\/<br\/>    static void printNGE(int arr[], int n)<br\/>    {<br\/>        int next, i, j;<br\/>        for (i=0; i&lt;n; i++)<br\/>        {<br\/>            next = -1;<br\/>            for (j = i+1; j&lt;n; j++)<br\/>            {<br\/>                if (arr[i] &lt; arr[j])<br\/>                {<br\/>                    next = arr[j];<br\/>                    break;<br\/>                }<br\/>            }<br\/>            System.out.println(arr[i]+&quot; -- &quot;+next);<br\/>        }<br\/>    }<br\/>      <br\/>    public static void main(String args[])<br\/>    {<br\/>        int arr[]= {11, 13, 21, 3};<br\/>        int n = arr.length;<br\/>        printNGE(arr, n);<br\/>    }<br\/>}<\/code><\/pre> <\/div>\n<p><strong>Output:<\/strong><\/p>\n<pre>11 -- 13\r\n13 -- 21\r\n21 -- -1\r\n3 -- -1<\/pre>\n<p>Time Complexity: O(n^2). The worst case occurs when all elements are sorted in decreasing order.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Java Algorithm &#8211; Next Greater Element &#8211; Stack &#8211; Given an array, print the Next Greater Element (NGE) for every element. The Next greater<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,73012,2139,79607],"tags":[81310,81305,81307,81303,81300,81299,81298,81302,81301,81304],"class_list":["post-27284","post","type-post","status-publish","format-standard","hentry","category-coding","category-data-structures","category-java","category-stack","tag-find-next-greater-number-in-array","tag-next-greater-element-algorithm","tag-next-greater-element-c","tag-next-greater-element-ideserve","tag-next-greater-element-in-array-java","tag-next-greater-element-leetcode","tag-next-greater-element-using-stack","tag-next-greater-element-using-stack-in-java","tag-next-greater-number","tag-next-smaller-element"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27284","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27284"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27284\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}