1.Given array A of size n.A triplet i,j,k is interesting if for evey i<p<j A[p]<A[i] and A[p]<A[j] and for every j<q<k A[q]<A[j] and A[q]<A[k]. Among all such interesting triplets find the maxium distance between k and i.(N<1e5) (Google)
2.An array of size n can have 3 values lets call them A,B,C.There are R requirements which demands exactly zi distinct values between xi and yi ,all these are of course input for R lines. How many such arrays are possible N<=300,R<=300 (Rubrik)
Can anyone give some ideas to approach these questions.
make 2 arrays val_left and val_right representing the leftmost and rightmost element bigger than current element (-1 if any element does not satisfy the case )
now use 2 pointer from both sides, such that val_left[L] and val_right[R] is non -1 value
now compute max bw elements at index L and R (both exclusive) — if max is greater than both elements (at L and R) you got the answer
else whichever element is bigger than that max, update it with next possible answer (L++ or R-- such that new value of L and R is non -1)