## Thursday, 27 August 2015

### 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.

Input : {0,1,2,6,8,87,12,43,23,54,66}

0 --> 87
1 --> 87
2 --> 87
6 --> 87
8 --> 87
87 --> -1
12 --> 66
43 --> 66
23 --> 66
54 --> 66
66 --> -1

package core.geeks;
import java.io.IOException;
public class NextGreatestElementUnsortedArr {
public static void main(String[] args) throws IOException {

int[] arr = new int[]{0,1,2,6,8,87,12,43,23,54,66};

int[] maxDynaArr = new int[arr.length];

maxDynaArr[arr.length-1] = -1;

if(arr[arr.length-1]>arr[arr.length-2]) {
maxDynaArr[arr.length-2] = arr[arr.length-1];
} else {
maxDynaArr[arr.length-2] = -1;
}

int preTemp = Math.max(Integer.MIN_VALUE, maxDynaArr[arr.length-2]);

for(int i=arr.length-3;i>=0;i--) {

int temp = Math.max(arr[i+1],maxDynaArr[i+2]);

preTemp = Math.max(preTemp,temp);
if(preTemp>arr[i]) {
maxDynaArr[i] = preTemp;
} else {
maxDynaArr[i] = -1;
}

}

for (int i = 0; i < maxDynaArr.length; i++) {
System.out.println(arr[i] + " --> "+maxDynaArr[i]);
}
}
}