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.
Java Programming:
[pastacode lang=”java” manual=”%2F%2F%20Simple%20Java%20program%20to%20print%20next%20%0A%2F%2F%20greater%20elements%20in%20a%20given%20array%0A%20%0Aclass%20Main%0A%7B%20%0A%20%20%20%20%2F*%20prints%20element%20and%20NGE%20pair%20for%20%0A%20%20%20%20%20all%20elements%20of%20arr%5B%5D%20of%20size%20n%20*%2F%0A%20%20%20%20static%20void%20printNGE(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20next%2C%20i%2C%20j%3B%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20-1%3B%0A%20%20%20%20%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%20%20%20%20%7B%0A%20%20%20%20%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%20%20%20%20%7B%0A%20%20%20%20%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%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(arr%5Bi%5D%2B%22%20–%20%22%2Bnext)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%3D%20%7B11%2C%2013%2C%2021%2C%203%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20printNGE(arr%2C%20n)%3B%0A%20%20%20%20%7D%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”]