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 the array. Elements for which no greater element exist, consider the next greater element as -1.
Examples:
- For an array, the rightmost element always has the next greater element as -1.
- For an array that is sorted in decreasing order, all elements have the next greater element as -1.
- 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
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 the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed.
Below is the implementation of the above approach:
PHP
<?php // Simple PHP program to print next // greater elements in a given array /* prints element and NGE pair for all elements of arr[] of size n */function printNGE($arr, $n) { for ($i = 0; $i < $n; $i++) { $next = -1; for ($j = $i + 1; $j < $n; $j++) { if ($arr[$i] < $arr[$j]) { $next = $arr[$j]; break; } } echo $arr[$i]." -- ". $next." "; } } // Driver Code $arr= array(11, 13, 21, 3); $n = count($arr); printNGE($arr, $n); // This code is contributed by Sam007 ?> |
11 -- 13 13 -- 21 21 -- -1 3 -- -1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Please refer complete article on Next Greater Element for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
