Simple cpp answer

programming
Tags: #<Tag:0x00007f1826b200a8>

#1

int validBST(vector &A,int i,int end){

if(i == end || i > end){
    return true;
}

int l=i;
while(l <= end && A[l] <= A[i]){
    l++;
}

l--;

if(l == i){
    l = -1;
}

int r=-1;

if(l!=end){
    if(l != -1)
        r=l+1;
    else
        r=i+1;
    while(r <= end && A[r] > A[i]){
        r++;
    }
    
    r--;

    if(r == l+1 && A[r] <= A[i]){
        r=-1;
    }
}

if(l != end && r != end){
    return 0;
}

bool left=true;
if(l != -1)
    left = validBST(A,i+1,l);

bool right=true;
if(r != -1){
    if(l != -1)
        right = validBST(A,l+1,end);
    else
        right = validBST(A,i+1,end);
}

if(left && right){
    return 1;
}else{
    return 0;
}

}

int Solution::solve(vector &A) {

int len=A.size();
return validBST(A,0,len-1);

}