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]);
              }
       }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...