{"id":27258,"date":"2018-01-05T22:14:51","date_gmt":"2018-01-05T16:44:51","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27258"},"modified":"2018-01-05T22:14:51","modified_gmt":"2018-01-05T16:44:51","slug":"c-algorithm-next-greater-element-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-next-greater-element-2\/","title":{"rendered":"Cpp Algorithm – Next Greater Element"},"content":{"rendered":"

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>Elements for which no greater element exist, consider next greater element as -1.<\/p>\n

Examples:
\na) <\/strong>For any array, rightmost element always has next greater element as -1.
\nb) <\/strong>For an array which is sorted in decreasing order, all elements have next greater element as -1.
\nc) <\/strong>For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.<\/p>\n

Element       NGE\r\n   4      -->   5\r\n   5      -->   25\r\n   2      -->   25\r\n   25     -->   -1\r\n<\/pre>\n
d)<\/strong> For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.<\/p>\n
  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
Method 1 (Simple)<\/strong>
\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
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
Output:<\/strong><\/p>\n
11 -- 13\r\n13 -- 21\r\n21 -- -1\r\n3 -- -1<\/pre>\n
Time Complexity: O(n^2). The worst case occurs when all elements are sorted in decreasing order.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
C++ Algorithm – Next Greater Element – Stack – Given an array, print the Next Greater Element (NGE) for every element. The Next greater 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":[81310,81308,81305,81307,81303,81300,81299,81298,81302,81301,81309,81304],"class_list":["post-27258","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-stack","tag-find-next-greater-number-in-array","tag-find-next-greater-number-with-same-set-of-digits-in-java","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-greater-permutation","tag-next-smaller-element"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27258","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=27258"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27258\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}