# Different and Easier Approach concept and code

#1

Use stacks to make the two arrays out of the input array - Next greatest element NGE and Next smallest element NSE. Now for each element in the array A, go directly to the j = NGE[i] and then start to look for a smaller element than the A[i] but don’t simply iterate through all the later elements instead keep on jumping to the NSE[j] till you find the element smaller than A[i]. This will bring down the time complexity from O(n*n) to O(n).

public class Solution {
public int solve(ArrayList A) {

``````    int[] ngeIndex = getNGE(A);
int size = A.size();
int[] nseIndex = getNSE(A);
// for(int i=0; i<size; i++)
// System.out.println(i+" - "+nseIndex[i]);

//for each element after the nge all elements should be greater

for(int i=size-1; i>=0; i--){

int n = A.get(i);
int j= ngeIndex[i];
while(j<size){
if(A.get(j)<n)
return 0;
j = nseIndex[j];
}

}
return 1;

}

public int[] getNGE(ArrayList<Integer> Arr){

Stack<Integer> st = new Stack<Integer>();
Stack<Integer> stind = new Stack<Integer>();

st.push(Arr.get(0));
stind.push(0);
int size = Arr.size();
int[] nge =  new int[size];

for(int i=1; i<size; i++){

if( Arr.get(i) > st.peek()){
while( !st.empty()){

if( Arr.get(i) > st.peek()){

nge[stind.pop()] = i;
st.pop();
}
else
break;
}
st.push(Arr.get(i));
stind.push(i);

}
else{
st.push(Arr.get(i));
stind.push(i);
}
}

//fill the ones in stack with -1
while(!st.empty()){
nge[stind.pop()]= size;
st.pop();
}

return nge;
}

public int[] getNSE(ArrayList<Integer> A){

Stack<Integer> st = new Stack<Integer>();
Stack<Integer> stind = new Stack<Integer>();

int size = A.size();
int[] nse = new int[size];

st.push(A.get(0));
stind.push(0);

for(int i=1; i<size; i++){

int n= A.get(i);

while( !st.empty()){
if( n < st.peek()){
nse[stind.pop()] = i;
st.pop();
}
else
break;
}
st.push(A.get(i));
stind.push(i);
}

while( !st.empty()){
nse[stind.pop()]=size;
st.pop();
}

return nse;
}
``````

}