{"id":27257,"date":"2018-01-05T22:13:39","date_gmt":"2018-01-05T16:43:39","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27257"},"modified":"2018-01-05T22:13:39","modified_gmt":"2018-01-05T16:43:39","slug":"c-algorithm-next-greater-element","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-next-greater-element\/","title":{"rendered":"C 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      -->   5\r\n   5      -->   25\r\n   2      -->   25\r\n   25     -->   -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      -->    -1\r\n   7       -->     12\r\n   6       -->     12\r\n   12     -->     -1<\/pre>\n[ad type=\u201dbanner\u201d]\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>C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Simple%20C%20program%20to%20print%20next%20greater%20elements%0A%2F%2F%20in%20a%20given%20array%0A%23include%3Cstdio.h%3E%0A%20%0A%2F*%20prints%20element%20and%20NGE%20pair%20for%20all%20elements%20of%0Aarr%5B%5D%20of%20size%20n%20*%2F%0Avoid%20printNGE(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20next%2C%20i%2C%20j%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20next%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%20i%2B1%3B%20j%3Cn%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3C%20arr%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20arr%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20printf(%22%25d%20\u2013%20%25d%5Cn%22%2C%20arr%5Bi%5D%2C%20next)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%3D%20%7B11%2C%2013%2C%2021%2C%203%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20printNGE(arr%2C%20n)%3B%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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=\u201dbanner\u201d]\n<strong>Method 2 (Using Stack)<\/strong><br \/>\nThanks to <a href=\"http:\/\/www.geeksforgeeks.org\/forum\/topic\/next-greater-element#post-2686\" target=\"_blank\" rel=\"noopener\">pchild <\/a>for suggesting following approach.<br \/>\n1) Push the first element to stack.<br \/>\n2) Pick rest of the elements one by one and follow following steps in loop.<br \/>\n\u2026.a) Mark the current element as <em>next<\/em>.<br \/>\n\u2026.b) If stack is not empty, then pop an element from stack and compare it with <em>next<\/em>.<br \/>\n\u2026.c) If next is greater than the popped element, then <em>next <\/em>is the next greater element for the popped element.<br \/>\n\u2026.d) Keep popping from the stack while the popped element is smaller than <em>next<\/em>. <em>next<\/em> becomes the next greater element for all such popped elements<br \/>\n\u2026.g) If <em>next <\/em>is smaller than the popped element, then push the popped element back.<br \/>\n3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.<\/p>\n<p><strong>C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Stack%20based%20C%20program%20to%20find%20next%20greater%20element%0A%2F%2F%20for%20all%20array%20elements.%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%23define%20STACKSIZE%20100%0A%20%0A%2F%2F%20stack%20structure%0Astruct%20stack%0A%7B%0A%20%20%20%20int%20top%3B%0A%20%20%20%20int%20items%5BSTACKSIZE%5D%3B%0A%7D%3B%0A%20%0A%2F%2F%20Stack%20Functions%20to%20be%20used%20by%20printNGE()%0Avoid%20push(struct%20stack%20*ps%2C%20int%20x)%0A%7B%0A%20%20%20%20if%20(ps-%3Etop%20%3D%3D%20STACKSIZE-1)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22Error%3A%20stack%20overflow%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20getchar()%3B%0A%20%20%20%20%20%20%20%20exit(0)%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20ps-%3Etop%20%2B%3D%201%3B%0A%20%20%20%20%20%20%20%20int%20top%20%3D%20ps-%3Etop%3B%0A%20%20%20%20%20%20%20%20ps-%3Eitems%20%5Btop%5D%20%3D%20x%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0Abool%20isEmpty(struct%20stack%20*ps)%0A%7B%0A%20%20%20%20return%20(ps-%3Etop%20%3D%3D%20-1)%3F%20true%20%3A%20false%3B%0A%7D%0A%20%0Aint%20pop(struct%20stack%20*ps)%0A%7B%0A%20%20%20%20int%20temp%3B%0A%20%20%20%20if%20(ps-%3Etop%20%3D%3D%20-1)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22Error%3A%20stack%20underflow%20%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20getchar()%3B%0A%20%20%20%20%20%20%20%20exit(0)%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20top%20%3D%20ps-%3Etop%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20ps-%3Eitems%20%5Btop%5D%3B%0A%20%20%20%20%20%20%20%20ps-%3Etop%20-%3D%201%3B%0A%20%20%20%20%20%20%20%20return%20temp%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20prints%20element%20and%20NGE%20pair%20for%20all%20elements%20of%0Aarr%5B%5D%20of%20size%20n%20*%2F%0Avoid%20printNGE(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20i%20%3D%200%3B%0A%20%20%20%20struct%20stack%20s%3B%0A%20%20%20%20s.top%20%3D%20-1%3B%0A%20%20%20%20int%20element%2C%20next%3B%0A%20%0A%20%20%20%20%2F*%20push%20the%20first%20element%20to%20stack%20*%2F%0A%20%20%20%20push(%26s%2C%20arr%5B0%5D)%3B%0A%20%0A%20%20%20%20%2F%2F%20iterate%20for%20rest%20of%20the%20elements%0A%20%20%20%20for%20(i%3D1%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20next%20%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(isEmpty(%26s)%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20if%20stack%20is%20not%20empty%2C%20then%20pop%20an%20element%20from%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20element%20%3D%20pop(%26s)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20the%20popped%20element%20is%20smaller%20than%20next%2C%20then%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20a)%20print%20the%20pair%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20b)%20keep%20popping%20while%20elements%20are%20smaller%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20stack%20is%20not%20empty%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(element%20%3C%20next)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf(%22%5Cn%20%25d%20\u2013%3E%20%25d%22%2C%20element%2C%20next)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if(isEmpty(%26s)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20element%20%3D%20pop(%26s)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20element%20is%20greater%20than%20next%2C%20then%20push%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20the%20element%20back%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(element%20%3E%20next)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20push(%26s%2C%20element)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20push%20next%20to%20stack%20so%20that%20we%20can%20find%0A%20%20%20%20%20%20%20%20%20%20%20next%20greater%20for%20it%20*%2F%0A%20%20%20%20%20%20%20%20push(%26s%2C%20next)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20After%20iterating%20over%20the%20loop%2C%20the%20remaining%0A%20%20%20%20%20%20%20elements%20in%20stack%20do%20not%20have%20the%20next%20greater%0A%20%20%20%20%20%20%20element%2C%20so%20print%20-1%20for%20them%20*%2F%0A%20%20%20%20while%20(isEmpty(%26s)%20%3D%3D%20false)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20element%20%3D%20pop(%26s)%3B%0A%20%20%20%20%20%20%20%20next%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20printf(%22%5Cn%20%25d%20\u2013%20%25d%22%2C%20element%2C%20next)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%3D%20%7B11%2C%2013%2C%2021%2C%203%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20printNGE(arr%2C%20n)%3B%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre> 11 -- 13\r\n 13 -- 21\r\n 3 -- -1\r\n 21 -- -1\r\n<\/pre>\n<p>Time Complexity: O(n). The worst case occurs when all elements are sorted in decreasing order. If elements are sorted in decreasing order, then every element is processed at most 4 times.<br \/>\na) Initially pushed to the stack.<br \/>\nb) Popped from the stack when next element is being processed.<br \/>\nc) Pushed back to the stack because next element is smaller.<br \/>\nd) Popped from the stack in step 3 of algo.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C Algorithm &#8211; Next Greater Element &#8211; Stack &#8211; Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79607],"tags":[81305,81307,81303,81300,81306,81299,81298,81302,81301,81304],"class_list":["post-27257","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-stack","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-java-leetcode","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\/27257","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=27257"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27257\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}