# PROBLEM LINK:

* Author and Editorialist:* Pankaj Sharma

# DIFFICULTY:

MEDIUM .

# PREREQUISITES:

Binary Search , Two- pointers , sliding window

# PROBLEM:

You have given two array of integers A and B.

F(L,R) = max(A_L,A_{L+1},... , A_R) - min(B_L,B_{L+1}, ... B_R)

G(k) = Total count of (L,R) such that F(L,R) <= k

Find min k such that G(k) = U

# QUICK EXPLANATION:

## Check

Calculate F(L,R) using sliding window + Two pointers.

For each r calculate leftmost valid l then calculate G(k) in O(N)

Then Apply binary on k

# EXPLANATION:

## Observation 1

If F(L,R) <=k then F(L+1,R) <=k ,…F(R,R)<=k because B_i \eq A_i and If we are at index R and move to left side then difference increases as we are taking max from A and min from B

## Observation 2

G(k) is monotonic on k i.e G(k) increases as k increases.

## Observation 3

min value of G(k) = 0 when none of (L,R) are valid

Max value of G(k) = n*(n+1)/2 when all (L,R) are valid

## How to approach

Using obervation 1 we can calculate F(L,R) in O(N)

How ?

Maintain two windows one is max(A[L…R]) and other is min(A[L…R)

This technique is known as Sliding Window

We will use two deque one for A and other for B for maintaining window.

Then for each R we will calculate leftmost valid L. This can be done by maintaining two pointers L and R.

max(A[L…R]) - min(A[L…R) >k then we will increment L by 1 as all L less that current L will also give F(L,R) i.e max(A[L…R]) - min(A[L…R) >k .

So We can calculate G(k) in O(N).

Then Using observation 2 and 3 we will apply binary on k from 0 to 1e9 to find first smallest k which will give G(k) = U.

You can learn it from Find first position of an element in a sorted array

# Time Complexity:

The time complexity is O(N*log(1e9)) per test case.

where N=total number of elements in array .

# SOLUTIONS:

## Editorialist's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll max(ll a, ll b) {return (a > b ? a : b);}
ll min(ll a, ll b) {return (a < b ? a : b);}
ll n, U;
vector<ll> a, b;
ll G(ll k) {
ll l = 1;
ll ans = 0, r;
deque<ll> max_A, min_B;
for ( r = 1; r <= n; r++) {
// Maintaining minimum in B
while ((!min_B.empty()) and b[min_B.back()] >= b[r])
min_B.pop_back();
// Maintaining max in A
while ((!max_A.empty()) and a[max_A.back()] <= a[r])
max_A.pop_back();
max_A.push_back(r);
min_B.push_back(r);
// Check if current window (l,r) have F(L,R)<=k or not
while ( a[max_A.front()] - b[min_B.front()] > k) {
l++;
if (min_B.front() < l)
min_B.pop_front();
if (max_A.front() < l)
max_A.pop_front();
if (l > n) {
break;
}
if ((max_A.empty()) or (min_B.empty())) break;
}
if (l > r) continue;
// Add all pair (l,r) to the answer
ans += (r - l + 1);
}
return ans;
}
void test_case() {
ll ans = -1;
ll l, r;
cin >> n >> U;
a = b = vector<ll>(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
ll mid, low = 0, high = 1e9 ;
// Binary search
while (low <= high) {
mid = (low + high) / 2;
ll now = G(mid);
if (now == U) {
ans = mid;
high = mid - 1;
}
else if (now > U) high = mid - 1;
else low = mid + 1;
}
cout << ans << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
test_case();
return 0;
}
```

Please give me suggestions if anything is unclear so that I can improve. Thanks