Cpp Algorithm – Next Greater Element

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

Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.

Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1

d) For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.

  Element        NGE
   13      -->    -1
   7       -->     12
   6       -->     12
   12     -->     -1

[ad type=”banner”]

Method 1 (Simple)
Use 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.

C++ Programming:

[pastacode lang=”c” manual=”%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–%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” message=”” highlight=”” provider=”manual”/]

Output:

11 -- 13
13 -- 21
21 -- -1
3 -- -1

Time Complexity: O(n^2). The worst case occurs when all elements are sorted in decreasing order.

[ad type=”banner”]