Given an array A of size N Integers, where A[i] represent height of (i)th building. if someone is in the ith building he can move to the jth building if i<j && A[i]<A[j]. Given Q queries, In the ith query in the form of two array U and V. where Ui and Vi represents position of alice and bob on the array. Alice is on U[i]th building and Bob is on the B[i]th building. You have to return minimum building number K that both alice and bob can move to. if not possible return -1;
Testcase Input N=3; 1 3 2 Q=3; U = 1 3 2 V = 2 1 3
output 2 3 -1
I approched this problem with segment tree lazy propagation but couldnt work out. Any help would be appreciated!
First we could break it down to 2 different cases. Since the relative position of Bob and Alice doesn't matter then for query i let u=min(U[i], V[i]) and u=max(U[i],V[i]):
Case 1: if a[u] < a[v], then whoever was at position u can go to position v since both condition are satisfied(we initially set u to the min and v the max) and it would be the answer.
Case 2: if a[u] >= a[v], then we need to find the first index j > v such that a[j] > a[u]. For this we could use a Segment Tree. We build a range max query segment tree where each node stores the max for the range. Then we binary search on the segment tree to find the range. Suppose the max of the range [v+1, n] is <= a[u] then the answer is -1, otherwise we check the left subsegment and the right subsegment. If the max of left subsegment > a[u] then we move to the left subsegment(since we want the first index in the range) otherwise we move to the right subsegment. Tc: O(logn)