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

}