# Next greater element

By | January 31, 2015
Share the joy
•
•
•
•
•
•

This one is from g4g. link
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.
This is actually a pratice for stack.

1. package feb;
2. import java.util.Stack;
3. public class NextGreaterElement {
4.     public static void main(String[] args) {
5.         int[] arr = { 11, 13, 3, 21, 7, 6, 4, 9, 12, 15 };
6.         Element[] arrEle = getNGE(arr);
7.         for (int i = 0; i < arrEle.length; i++) {
8.             System.out.println(arrEle[i]);
9.         }
10.     }
11.     /*
12.      * http://www.geeksforgeeks.org/next-greater-element/ Using stack pratice.
13.      * Given an array, print the Next Greater Element (NGE) for every element.
14.      * The Next greater Element for an element x is the first greater element on
15.      * the right side of x in array. Elements for which no greater element
16.      * exist, consider next greater element as -1. Examples: a) For any array,
17.      * rightmost element always has next greater element as -1. b) For an array
18.      * which is sorted in decreasing order, all elements have next greater
19.      * element as -1. c) For the input array [4, 5, 2, 25}, the next greater
20.      * elements for each element are as follows.
21.      *
22.      * Element NGE
23.      * 4 –> 5
24.      * 5 –> 25
25.      * 2 –> 25
26.      * 25 –> -1
27.      *
28.      * d) For the input array
29.      * [13, 7, 6, 12}, the next greater elements for each element are as
30.      * follows.     *
31.      * Element NGE
32.      * 13 –> -1
33.      * 7 –> 12
34.      * 6 –> 12
35.      * 12 –> -1
36.      */
37.     public static Element[] getNGE(int[] arr) {
38.         if (arr == null) {
39.             return null;
40.         }
41.         Element[] arrEle = new Element[arr.length];
42.         for (int i = 0; i < arr.length; i++) {
43.             arrEle[i] = new Element(arr[i], i);
44.         }
45.         Stack<Element> s = new Stack<Element>();
46.         s.push(arrEle);
47.         for (int i = 1; i < arrEle.length; i++) {
48.             while (!s.empty() && arrEle[i].value > s.peek().value) {
49.                 Element ele = s.pop();
50.                 arrEle[ele.pos].nge = arrEle[i].value;
51.             }
52.             s.push(arrEle[i]);
53.         }
54.         // rest elements in stack has no next larger element.
55.         while (!s.empty()) {
56.             Element ele = s.pop();
57.             arrEle[ele.pos].nge = -1;
58.         }
59.         return arrEle;
60.     }
61.     static class Element {
62.         int value;
63.         int nge;
64.         int pos;
65.         Element(int value, int pos) {
66.             this.value = value;
67.             this.pos = pos;
68.         }
69.         @Override
70.         public String toString() {
71.             return value + “\t” + nge;
72.         }
73.     }
74. }