649. The Furthest Pair That Still Works
Two NON-INCREASING lists are given. A pair of positions (i, j) is VALID when i <= j and
a[i] <= b[j].
Print the largest j - i over all valid pairs, or 0 when none exists.
a = 55 30 5 4 2, b = 100 20 10 10 5 -> 2 i = 2, j = 4
a = 8 8 8, b = 8 8 8 8 8 -> 4
a = 5 4, b = 3 2 -> 0
## Both pointers move forward, and neither resets
i = 0, j = 0, best = 0
while i < n and j < m:
if a[i] > b[j]: i += 1 this i cannot work with this j
else: best = max(best, j - i); j += 1
if i > j: j = i keep j from falling behind i
## Why i never needs to go back
Suppose a[i] > b[j]. Then i cannot pair with j. It cannot pair with any LATER j either,
because b is non-increasing, so every later b[j] is no larger and the comparison only gets
worse.
So i is finished with every remaining j, and advancing it loses nothing. That is the whole
argument, and it is the non-increasing order of b that supplies it.
## Why advancing j after a success is right
When a[i] <= b[j] the distance j - i has been recorded. Keeping this i and trying a larger
j can only lengthen the distance, so j advances while i stays. If the larger j fails,
the first branch then advances i, and the sweep continues without either pointer rewinding.
## Why a smaller i is never worth revisiting
Because a is also non-increasing, a smaller i has an a-value that is at least as LARGE, so
it is harder to satisfy, not easier. Any pair a smaller i could form with the current j
would have been found when that i was current.
## The guard that keeps j ahead
The definition requires i <= j, so if i overtakes j the pair is not allowed. Pushing j
up to i restores the requirement and costs nothing, because a j below i could not have
been used anyway.
Without it the answer can come out negative, which is the symptom to look for.
## Boundaries
No valid pair gives 0, and so does a valid pair with i == j. The two cases are
indistinguishable in the output, which is what the statement means by "or 0 when none exists".
## Cost
Time O(n + m). Space O(1).
Constraints - `1 ≤ n, m ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - both lists are non-increasing
Input
The first line contains two integers n and m.
The second line contains n integers in non-increasing order.
The third line contains m integers in non-increasing order.
Output
Print one integer, the largest j - i over valid pairs, or 0 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.