O(n) solution is giving TLE, what am I missing in this?


#1

bool greater_(vector &a,int start,int end,int x){
for(int i=start;i<=end;i++){
if(x>=a[i]) return false;
}
return true;
}

void nextGreater(vector &a,vector &ans){
stack s;
int n=a.size(),tmp,i;
s.push(n-1);

for(i=n-2;i>=0;i--){
    while(s.size()){
        tmp=s.top();
        if(a[i]>a[tmp]){
            s.pop();
        }
        else{
            ans[i]=tmp;
        }
    }
    s.push(i);
}

}
int util(vector &A,int start,int end,vector &ng){
if(start>=end) return true;
int pivot=ng[start];
if(pivot==-1) return util(A,start+1,end,ng);
if(greater_(A,pivot,end,A[start])){
return util(A,start+1,pivot-1,ng) && util(A,pivot,end,ng);

}
return false;

}

int Solution::solve(vector &A) {
// 6
// 3 10
// 1 4 8 13
// 7

//6 3 1 4 10 8 7 13
//(3,1,4) (10,8,7,13)
//(1)(4)   (8,7) (13)
int n=A.size(),pivot;
vector<int> ng(n,-1);
nextGreater(A,ng);
return util(A,0,n-1,ng); 

}