LeetCode 1855 - Maximum Distance Between a Pair of Values

LeetCode Problem 1855

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search

Solution

Problem Understanding

You are given two integer arrays, nums1 and nums2, and both arrays are sorted in non-increasing order. That means the values either stay the same or decrease as we move from left to right.

A pair of indices (i, j) is considered valid if two conditions are satisfied:

1. i <= j
2. nums1[i] <= nums2[j]

For every valid pair, the distance is defined as:

$$j - i$$

The goal is to find the maximum possible distance among all valid pairs. If no valid pair exists, the answer is 0.

The important detail is that both arrays are already sorted in descending order. This structure is what allows us to design an efficient algorithm.

For example, suppose:

nums1 = [55,30,5,4,2]
nums2 = [100,20,10,10,5]

If we choose i = 2 and j = 4:

nums1[2] = 5
nums2[4] = 5

Since:

2 <= 4
5 <= 5

the pair is valid, and the distance is:

4 - 2 = 2

The constraints are large:

1 <= nums1.length, nums2.length <= 100000

This immediately tells us that a quadratic solution will be too slow. An $O(n \times m)$ solution could require up to $10^{10}$ operations in the worst case, which is far beyond acceptable limits.

The problem guarantees:

• Both arrays are non-empty
• Values are positive integers
• Arrays are already sorted in non-increasing order

These guarantees are extremely important because the sorted order enables efficient pointer movement and binary search optimizations.

Several edge cases are important:

• No valid pairs exist
• Arrays have only one element
• All pairs are valid
• Arrays contain many duplicate values
• nums1 is much shorter or much longer than nums2

A correct solution must handle all of these efficiently.

Approaches

Brute Force Approach

The most direct solution is to check every possible pair (i, j).

For every index i in nums1, we iterate through every index j in nums2. For each pair, we verify:

i <= j
nums1[i] <= nums2[j]

If the pair is valid, we compute the distance j - i and update the maximum answer.

This approach is correct because it exhaustively examines all possible pairs. No valid pair can be missed.

However, its performance is unacceptable for the given constraints. If both arrays contain 100000 elements, the nested loops require up to:

$$100000 \times 100000 = 10^{10}$$

comparisons.

That is far too slow.

Optimal Two Pointers Approach

The key observation comes from the sorted order of both arrays.

Because the arrays are non-increasing:

• Moving right in either array never increases the values
• Once a condition fails for a certain pointer configuration, we can often move pointers intelligently without revisiting previous states

We use two pointers:

• i for nums1
• j for nums2

The strategy is:

• Expand j as far as possible while the pair remains valid
• If the pair becomes invalid, move i forward
• Ensure j >= i at all times

This works because both pointers only move forward. No pointer ever moves backward, which guarantees linear time complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Checks every possible pair
Optimal Two Pointers	O(n + m)	O(1)	Uses sorted property to move pointers efficiently

Algorithm Walkthrough

Optimal Two Pointers Algorithm

1. Initialize two pointers:

• i = 0 for nums1
• j = 0 for nums2

Also initialize:

• max_distance = 0

2. Continue while both pointers are inside their arrays.
3. At each step, check whether the current pair (i, j) is valid:

• i <= j
• nums1[i] <= nums2[j]

4. If the pair is valid:

• Compute the distance j - i
• Update max_distance
• Move j forward to try achieving a larger distance

5. If the pair is invalid:

• Move i forward because nums1[i] is too large
• If i becomes greater than j, move j to match i

6. Continue until one pointer reaches the end of its array.
7. Return max_distance.

Why it works

The algorithm relies on the monotonic ordering of both arrays.

When a pair (i, j) is valid, increasing j may produce a larger distance, so we keep expanding.

When a pair becomes invalid, increasing j further cannot help because nums2[j] can only stay the same or decrease. Therefore, the only way to restore validity is to move i forward.

Since each pointer moves only forward and never backward, every array position is processed at most once. This guarantees linear time complexity while still exploring all potentially optimal pairs.

Python Solution

from typing import List

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        i = 0
        j = 0
        max_distance = 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] <= nums2[j]:
                max_distance = max(max_distance, j - i)
                j += 1
            else:
                i += 1

                if i > j:
                    j = i

        return max_distance

The implementation directly follows the two pointers strategy.

We maintain two indices, i and j, representing positions in nums1 and nums2.

Inside the loop, we first test whether the current pair is valid.

If it is valid, we update the answer and move j forward because increasing j increases the distance.

If the pair is invalid, nums1[i] is too large compared to nums2[j]. Since nums2 is non-increasing, moving j further right will not increase its value. Therefore, we move i forward instead.

The adjustment:

if i > j:
    j = i

ensures that the condition i <= j is always maintained.

Because both pointers move only forward, the total number of iterations is linear.

Go Solution

func maxDistance(nums1 []int, nums2 []int) int {
    i := 0
    j := 0
    maxDistance := 0

    for i < len(nums1) && j < len(nums2) {
        if nums1[i] <= nums2[j] {
            if j-i > maxDistance {
                maxDistance = j - i
            }
            j++
        } else {
            i++

            if i > j {
                j = i
            }
        }
    }

    return maxDistance
}

The Go implementation mirrors the Python logic almost exactly.

Slices in Go behave similarly to dynamic arrays, so index access remains straightforward.

There are no integer overflow concerns because the maximum possible distance is at most 100000, which easily fits inside Go's int type.

Unlike Python, Go requires explicit variable declarations and manual maximum comparisons instead of using the built-in max() function.

Worked Examples

Example 1

nums1 = [55,30,5,4,2]
nums2 = [100,20,10,10,5]

Step	i	j	nums1[i]	nums2[j]	Valid?	Distance	max_distance
1	0	0	55	100	Yes	0	0
2	0	1	55	20	No	-	0
3	1	1	30	20	No	-	0
4	2	2	5	10	Yes	0	0
5	2	3	5	10	Yes	1	1
6	2	4	5	5	Yes	2	2

Final answer:

2

Example 2

nums1 = [2,2,2]
nums2 = [10,10,1]

Step	i	j	nums1[i]	nums2[j]	Valid?	Distance	max_distance
1	0	0	2	10	Yes	0	0
2	0	1	2	10	Yes	1	1
3	0	2	2	1	No	-	1
4	1	2	2	1	No	-	1
5	2	2	2	1	No	-	1

Final answer:

1

Example 3

nums1 = [30,29,19,5]
nums2 = [25,25,25,25,25]

Step	i	j	nums1[i]	nums2[j]	Valid?	Distance	max_distance
1	0	0	30	25	No	-	0
2	1	1	29	25	No	-	0
3	2	2	19	25	Yes	0	0
4	2	3	19	25	Yes	1	1
5	2	4	19	25	Yes	2	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each pointer moves forward at most once through its array
Space	O(1)	Only a few variables are used

The algorithm is linear because neither pointer ever moves backward.

Pointer i moves at most len(nums1) times, and pointer j moves at most len(nums2) times.

Therefore, the total work is proportional to:

$$O(len(nums1) + len(nums2))$$

The algorithm uses constant extra memory because it stores only a few integer variables.

Test Cases

from typing import List

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        i = 0
        j = 0
        max_distance = 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] <= nums2[j]:
                max_distance = max(max_distance, j - i)
                j += 1
            else:
                i += 1

                if i > j:
                    j = i

        return max_distance

solution = Solution()

assert solution.maxDistance(
    [55,30,5,4,2],
    [100,20,10,10,5]
) == 2  # example 1

assert solution.maxDistance(
    [2,2,2],
    [10,10,1]
) == 1  # example 2

assert solution.maxDistance(
    [30,29,19,5],
    [25,25,25,25,25]
) == 2  # example 3

assert solution.maxDistance(
    [5],
    [5]
) == 0  # single valid pair

assert solution.maxDistance(
    [10],
    [5]
) == 0  # no valid pair

assert solution.maxDistance(
    [1,1,1],
    [10,10,10]
) == 2  # all pairs valid

assert solution.maxDistance(
    [10,9,8],
    [1,1,1]
) == 0  # completely invalid arrays

assert solution.maxDistance(
    [5,4,3],
    [5,4,3]
) == 0  # only diagonal pairs valid

assert solution.maxDistance(
    [4,3,2],
    [10,9,8,7,6]
) == 4  # maximum distance uses farthest j

assert solution.maxDistance(
    [100000],
    [100000]
) == 0  # maximum value constraint

assert solution.maxDistance(
    [6,5,4],
    [9,8,7,3]
) == 2  # valid until last position

Test Summary

Test	Why
[55,30,5,4,2], [100,20,10,10,5]	Validates standard mixed behavior
[2,2,2], [10,10,1]	Tests duplicate values
[30,29,19,5], [25,25,25,25,25]	Tests increasing valid distance
[5], [5]	Smallest valid input
[10], [5]	Smallest invalid input
[1,1,1], [10,10,10]	Every pair valid
[10,9,8], [1,1,1]	No valid pairs
[5,4,3], [5,4,3]	Only equal-index pairs valid
[4,3,2], [10,9,8,7,6]	Maximum distance near array end
[100000], [100000]	Tests upper value bound
[6,5,4], [9,8,7,3]	Valid pairs disappear late

Edge Cases

One important edge case occurs when no valid pair exists. For example:

nums1 = [10,9,8]
nums2 = [1,1,1]

Every value in nums1 is larger than every value in nums2, so the condition nums1[i] <= nums2[j] is never satisfied. A buggy implementation might accidentally produce a negative distance or fail to handle this cleanly. The current implementation correctly returns 0 because max_distance starts at 0 and is updated only for valid pairs.

Another important edge case is when all pairs are valid. Consider:

nums1 = [1,1,1]
nums2 = [10,10,10]

Every comparison succeeds, so the algorithm continually expands j. The maximum distance becomes the largest possible value, 2. This case validates that the algorithm correctly explores farther indices instead of stopping at the first valid pair.

A third important edge case occurs when pointer synchronization becomes necessary. Suppose:

nums1 = [100]
nums2 = [1,1,1]

Initially, (0,0) is invalid, so i moves forward. Without careful handling, j could become smaller than i, violating the required condition i <= j. The implementation prevents this using:

if i > j:
    j = i

This guarantees that future comparisons always satisfy the index ordering requirement.

Another subtle edge case involves duplicate values. Arrays like:

nums1 = [5,5,5]
nums2 = [5,5,5,5]

contain many equivalent comparisons. Some implementations accidentally skip valid distances when equal values appear repeatedly. The two pointers approach handles duplicates naturally because equality is explicitly allowed by the condition:

nums1[i] <= nums2[j]

As a result, the algorithm correctly discovers the farthest valid pair.