Efficient way to find min(max(A[L], A[L+1],...,A[R]), min(B[L], B[L+1],…, B[R]))

user_16077632 0
Viewed 85

Given 2 array A[N] and B[N]. For each 0 <= L < N <= 5e5, find the maximum value of

min(max(A[L], A[L+1],...,A[R]), min(B[L], B[L+1],…, B[R]))

for L <= R <= N.

ans[L] is the answer for L.
For example,
N = 3
A[3] = {3, 2, 1}
B[3] = {3, 2, 3}
So, the answer is
ans[0] = 3
ans[1] = 2
ans[2] = 1

It is clear that brute-forces can run fast.
Then, I tried using Sparse table, Segment Tree or Binary Indexed Tree (and we don't need to update anything, so I choose Sparse Table). But for each L, we don't know R, so I need to run to the end of the array, and this doesn't different from brute-forces .

Is there any efficient algorithm or data structures for this problem??

P/s: Sorry for my bad English.

max min algorithm
2 Answers

Using Sparse table A is monotone increasing, B is monotone decreasing, so we need to find the crossing point to get the max out of their min ...

pseudo python code untested

stA = SparseTable(A);
stB = SparseTable(B);

for (i in range(len(A))
  r = len(B)
  l = i

  a = stA.max(l,r)
  b = stB.min(l,r)

  # binary search for crossing point
  while (l != r)
    m = l + (r-l)//2  # integer division 
    a = stA.max(l,m)
    b = stB.min(l,m)
    if (b > a)
      l = m + 1
    else
      r = m

  ans[i] = min(a,b) # might be off-by-one m?
user_40132580

max(A[L], A[L+1], ..., A[R]) is non-increasing in L and non-decreasing in R. Conversely, min(B[L], B[L+1], ..., B[R]) is non-decreasing in L and non-increasing in R. It follows that the function from L to the argmax in R is non-decreasing. The last ingredient is two queues, one that can report max, one that can report min, to quickly compute the sliding window aggregates.

user_21446690
Related