Given an array, print the Next Greater Element (NGE) for every 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:
i.   For any array, rightmost element always has next greater element as -1.
ii.  For an array which is sorted in decreasing order, all elements have next greater element as -1.
iii. For the input array {1,4,3,6,7} the next greater elements for each element are as follows.

Element NGE
1 4
4 6
3 6
6 7
7 -1

Algorithm :

1. Iterate over the array arr[] for i = 0 to (arr.length -1 ).

    1.1  If the stack is empty then push the element in stack.
    1.2  Else if the stack is not empty and stack top is less than current element arr[i]
        1.2.1  NGE found for current stack top. The current element is greater than stack top.
        1.2.2  Print (stack.pop() and arr[i]). Remember stack.pop() will remove the current top.
        Repeat 1.2.1 and 1.2.2 for next Stack Top. All the elements present in the stack are in the left side of current element in the input array. And if current element is greater than stack entries then current element is the NGE.
        1.2.3 Push the current element in the stack
2. At this step elements left in the stack , do not have any NGE.

Now let us check with some data for this algorithm. Consider our input array is arr[ ] = {1,4,3,6,7}

remember stack.pop() will remove the element from the stack.

Step 1 : arr[0] := 1 push in stack. Current Stack = [1].
Step 2 : arr[1] := 4 is greater than Stack top.
         So print stack.pop() and arr[1] --> print (1 -- 4)
         push the element in stack. Current Stack = [4].
Step 3 : arr[2] := 3. Less than stack top. Thus push in stack. Current Stack [4,3]
Step 4 : arr[3] := 6 is greater than Stack top.
         So print stack.pop() and arr[3] --> print (3 -- 6). Current Stack [4]
         arr[3] := 6 is greater than Stack top.
         So print stack.pop() and arr[3] --> print (4 -- 6). Current Stack []
         push the element in stack. Current Stack = [6].
Step 5 : arr[4] := 7 is greater than Stack top.
         So print stack.pop() and arr[4] --> print (6 -- 7). Current Stack [7]
Step 6 : No NGE present for 7. Print ( 7 -- -1)

Now let us check the implementation of the algorithm. We are using a this STACK ADT to solve the problem.

public class FindNextGreatest {

 public static void ngeLeftToRight(int[] a) throws Exception {
  ArrayStack < Integer > myStack = new ArrayStack < Integer > ();
  for (int i = 0; i < a.length; i++) {
   if (myStack.isEmpty())
    myStack.push(a[i]);
   else {
    while (!myStack.isEmpty() && myStack.top() < a[i]) {
     System.out.println(myStack.pop() + " --> " + a[i]);
    }
    myStack.push(a[i]);
   }
  }
  while (!myStack.isEmpty())
   System.out.println(myStack.pop() + " --> -1");
 }

 public static void main(String[] arg) throws Exception {
  int[] a = {
   6,
   3,
   9,
   1,
   5,
   10,
   4,
   8,
   7,
   2
  };
  ngeLeftToRight(a);
 }
}

Now check the Output :

3   --> 9
6   --> 9
1   --> 5
5   --> 10
9   --> 10
4   --> 8
2   --> -1
7   --> -1
8   --> -1
10  --> -1

 

core java 12 Algorithm 12 Arrays 12

FOLLOW US ON LinkedIn



Explore Tutu'rself