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.
Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) 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
package nextGreaterElement; import java.util.Stack; public class NGE // next greater element { public static void main(String[] args) { int A[]={7,8,9,4,5,6,1,2,3}; Stack<Integer> S=new Stack<Integer>(); S.push(new Integer(A[0])); for(int i=1;i<A.length;i++) { int current=A[i]; while(true) { if(S.isEmpty()) { S.push(new Integer(current)); break; } int element=S.pop().intValue(); if(element>current) { S.push(new Integer(element)); S.push(new Integer(current)); break; } System.out.println(element+" -> "+current); } } while(!S.isEmpty()) System.out.println(S.pop()+" -> "+"-1"); } }
Time Complexity : O(n)
Note that when you use two loops to iterate through the array to find the next greater element your time complexity will be O(n*n), but by using the above mentioned method of stacks, we can reduce the time complexity to O(n).
No comments:
Post a Comment