Farthest pair across two falling lists

Scenario

A budgeting app tracks two prepaid cards, Card A and Card B. At the end of each month it saves each card's balance in whole units. Nobody tops up either card, so a balance never rises from one month to the next.

A "safe to switch" tip compares one month of Card A with the same or a later month of Card B. It looks for the pair of months that are furthest apart where Card B still holds at least as much as Card A held. You are asked to find that distance.

Your task

Write widest_valid_gap(first, second).

first[i] is the balance of Card A at the end of month i. Each balance is no higher than the one before it. Equal balances are allowed.
second[j] is the balance of Card B at the end of month j, in the same form. The two lists may have different lengths.
A pair of months (i, j) is valid when i <= j and first[i] <= second[j]. Its gap is j - i.
Return the largest gap over all valid pairs. Return 0 if no pair is valid.

Examples

Example 1 (traced)#

text2 lines

Input:  first = [40, 35, 30, 10, 5], second = [95, 65, 60, 50, 40, 30, 15]
Output: 4

Pointers i and j start at 0. If first[i] is above second[j], no later month of the second list can match it, so i moves on. Otherwise the pair is valid: record j - i, then move j.

i	j	first[i]	second[j]	Compared	Gap	best after	Move
0	0	40	95	fits	0	0	j becomes 1
0	1	40	65	fits	1	1	j becomes 2
0	2	40	60	fits	2	2	j becomes 3
0	3	40	50	fits	3	3	j becomes 4
0	4	40	40	fits	4	4	j becomes 5
0	5	40	30	too high		4	i becomes 1
1	5	35	30	too high		4	i becomes 2
2	5	30	30	fits	3	4	j becomes 6
2	6	30	15	too high		4	i becomes 3
3	6	10	15	fits	3	4	j becomes 7, the walk ends

The best pair is month 0 of the first list and month 4 of the second: both hold 40, and the gap is 4.

Example 2#

text2 lines

Input:  first = [50, 50], second = [50, 50, 50, 50]
Output: 3

Equal balances match. Month 0 of the first list and month 3 of the second list give a gap of 3.

Example 3#

text2 lines

Input:  first = [5], second = [4, 3]
Output: 0

Card B never reaches 5, so no pair is valid and the answer is 0.

Constraints

1 ≤ first.length ≤ 100,000 and 1 ≤ second.length ≤ 100,000 (months of history)
1 ≤ first[i], second[j] ≤ 100,000 (balances in whole units)
Each list never rises: first[i] ≥ first[i + 1] and second[j] ≥ second[j + 1]

What does n ≤ 10^5 tell you?

Checking every pair of months costs about n × n ÷ 2 pairs. At n = 100,000 that is 5 × 10^9, about 50 seconds at 10^8 operations a second. A walk that moves one pointer per step makes at most 200,000 steps.

The answer is at most 99,999, so it fits easily in a 32-bit integer.

Scenario

Your task

Write widest_valid_gap(first, second).

first[i] is the balance of Card A at the end of month i. Each balance is no higher than the one before it. Equal balances are allowed.
second[j] is the balance of Card B at the end of month j, in the same form. The two lists may have different lengths.
A pair of months (i, j) is valid when i <= j and first[i] <= second[j]. Its gap is j - i.
Return the largest gap over all valid pairs. Return 0 if no pair is valid.

Examples

Example 1 (traced)#

text2 lines

Input:  first = [40, 35, 30, 10, 5], second = [95, 65, 60, 50, 40, 30, 15]
Output: 4

Pointers i and j start at 0. If first[i] is above second[j], no later month of the second list can match it, so i moves on. Otherwise the pair is valid: record j - i, then move j.

i	j	first[i]	second[j]	Compared	Gap	best after	Move
0	0	40	95	fits	0	0	j becomes 1
0	1	40	65	fits	1	1	j becomes 2
0	2	40	60	fits	2	2	j becomes 3
0	3	40	50	fits	3	3	j becomes 4
0	4	40	40	fits	4	4	j becomes 5
0	5	40	30	too high		4	i becomes 1
1	5	35	30	too high		4	i becomes 2
2	5	30	30	fits	3	4	j becomes 6
2	6	30	15	too high		4	i becomes 3
3	6	10	15	fits	3	4	j becomes 7, the walk ends

The best pair is month 0 of the first list and month 4 of the second: both hold 40, and the gap is 4.

Example 2#

text2 lines

Input:  first = [50, 50], second = [50, 50, 50, 50]
Output: 3

Equal balances match. Month 0 of the first list and month 3 of the second list give a gap of 3.

Example 3#

text2 lines

Input:  first = [5], second = [4, 3]
Output: 0

Card B never reaches 5, so no pair is valid and the answer is 0.

Constraints

1 ≤ first.length ≤ 100,000 and 1 ≤ second.length ≤ 100,000 (months of history)
1 ≤ first[i], second[j] ≤ 100,000 (balances in whole units)
Each list never rises: first[i] ≥ first[i + 1] and second[j] ≥ second[j + 1]

What does n ≤ 10^5 tell you?

The answer is at most 99,999, so it fits easily in a 32-bit integer.