Widest Two-Track Gap

Medium

You are given two integer arrays first and second of the same length. The gap of a pair of indices i and j is |first[i] - first[j]| + |second[i] - second[j]| + |i - j|. Return the largest gap over all pairs 0 ≤ i, j < len(first). Checking every pair takes O(n²); try to find a linear solution.

Example 1

first=[3, -1, 4], second=[0, 2, -2] → 10

Indices 1 and 2: |-1 - 4| + |2 - (-2)| + |1 - 2| = 5 + 4 + 1 = 10.

Example 2

first=[5, 5], second=[7, 7] → 1

The values are equal, so only the index distance counts: 1.

Constraints

2 ≤ len(first) == len(second) ≤ 40,000
-10⁶ ≤ first[i], second[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math

Similar problems

Turn a Square Clockwise Medium Postfix Calculator Medium Roll an Array to the Right Medium Primes Below a Bound Medium Nth Number Built From Given Primes Medium

Input

first=[3, -1, 4], second=[0, 2, -2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.