Maximum Distance Between a Pair of Values: Two Pointer Sweep

LeetCode 1855, Maximum Distance Between a Pair of Values, is a clean two-pointer problem that takes advantage of sorted (non-increasing) input. You are scanning two arrays in lockstep, and the sorted order lets you make greedy decisions about which pointer to advance. If you have solved Two Sum II or Container With Most Water, you already own the building block this problem is built on.

The problem

You are given two non-increasing integer arrays nums1 and nums2. A pair of indices (i, j) is valid if:

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

The distance of a valid pair is j - i. Return the maximum distance among all valid pairs, or 0 if no valid pair exists.

Both arrays are sorted in non-increasing order, meaning each element is >= the one after it.

In the example above, nums1 = [55, 30, 5, 4, 2] and nums2 = [100, 20, 10, 10, 5]. The best valid pair is (i=2, j=4) because nums1[2] = 5 <= nums2[4] = 5 and the distance is 4 - 2 = 2.

Brute force: check every pair

The simplest approach: try every (i, j) pair where i <= j, check the condition, and track the maximum distance.

def max_distance_brute(nums1, nums2):
    best = 0
    for i in range(len(nums1)):
        for j in range(i, len(nums2)):
            if nums1[i] <= nums2[j]:
                best = max(best, j - i)
    return best

This runs in O(n * m) time. For arrays with up to 100,000 elements each, that is up to 10 billion comparisons. Way too slow.

Two pointer sweep: O(n + m)

Here is the key insight: both arrays are non-increasing. That means as you move right in either array, values can only get smaller or stay the same. This lets you sweep both arrays left to right with two pointers without ever needing to backtrack.

The algorithm:

1. Start both i and j at 0.
2. If nums1[i] <= nums2[j], the pair is valid. Record j - i as a candidate (if it is positive). Advance j to try extending the distance further.
3. If nums1[i] > nums2[j], the pair is invalid. Advance i to try a smaller value from nums1.
4. Stop when either pointer runs past the end of its array.

Why does this work? Because nums1 is non-increasing, advancing i gives you a value that is <= the current one, which makes the condition nums1[i] <= nums2[j] easier to satisfy. And because nums2 is non-increasing, advancing j only makes nums2[j] smaller. So once nums1[i] > nums2[j], advancing j would only make things worse. The only productive move is to advance i.

def max_distance(nums1, nums2):
    i, j = 0, 0
    best = 0

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

    return best

Each iteration advances either i or j by one. Since i can go up to len(nums1) and j can go up to len(nums2), the total number of iterations is at most n + m.

Visual walkthrough

Let's trace the algorithm on nums1 = [55, 30, 5, 4, 2] and nums2 = [100, 20, 10, 10, 5]. The highlighted cell in each row marks the current pointer position.

Notice how i jumps from 0 to 2 in the early steps because nums1[0] = 55 and nums1[1] = 30 are both too large for any remaining nums2 values. Once i lands on the smaller values at index 2, the j pointer sweeps all the way to the end of nums2 and picks up the maximum distance of 2.

Why two pointers never miss the answer

The correctness argument boils down to two observations:

1. When nums1[i] > nums2[j], advancing j cannot help. Since nums2 is non-increasing, nums2[j+1] <= nums2[j]. If nums1[i] already exceeds nums2[j], it will also exceed everything to the right. The only way to satisfy the condition is to make nums1[i] smaller by advancing i.

2. When nums1[i] <= nums2[j], we record the distance and advance j. We do not need to try other i values for this j because j - i only gets smaller as i increases. The current i already gives the best distance for this j. Advancing j is the only way to potentially find a larger distance.

Together, these two rules guarantee that every pointer move either records the best possible distance for the current position or eliminates positions that cannot improve the answer. No valid pair is skipped.

Complexity analysis

Time: O(n + m). Each step advances one of the two pointers forward. Pointer i advances at most n times and pointer j advances at most m times, where n = len(nums1) and m = len(nums2).

Space: O(1). Three variables: i, j, best. No extra data structures.

The building blocks

This problem uses one core technique that appears in many LeetCode problems at the medium and hard level.

Co-directional two pointers on sorted input

Both pointers start at the same end and move in the same direction. The sorted order tells you which pointer to advance at each step. You never need to backtrack because the monotonicity of both arrays guarantees that skipped positions cannot improve the result.

This same idea drives:

• Merge two sorted arrays (advance the pointer with the smaller value)
• Intersection of two sorted arrays (advance the pointer with the smaller value to catch up)
• Remove duplicates from sorted array (a read pointer and a write pointer moving forward together)

The key difference from opposite-end convergence (like Container With Most Water or Two Sum II) is that both pointers move in the same direction. The invariant is simpler: at every step, the pointer you advance is the only one that can potentially improve the situation.

Edge cases

A few things to watch for:

• No valid pairs. If nums1[0] > nums2[0], the very first element of nums1 already exceeds the largest element of nums2. The two-pointer sweep will just keep advancing i until it runs out, and best stays 0.
• All pairs valid. If every element of nums1 is <= every element of nums2, the maximum distance is min(len(nums1), len(nums2)) - 1 (the last valid j minus i = 0). The sweep will find this on the first pass.
• Single-element arrays. nums1 = [5], nums2 = [5]. One valid pair (0, 0) with distance 0. The code handles this correctly.
• Arrays of different lengths. The pointers stop as soon as either array is exhausted. No index-out-of-bounds issues.

From reading to recall

You have seen the algorithm, traced through the example, and understood why it works. But the details will fade. Which pointer do you advance when the condition is met? Which one when it is not? What if j ends up behind i?

These are small details, but getting any one of them wrong in an interview means a broken solution. The fix is to practice writing the code from memory a few times over the next couple of weeks. The two-pointer sweep on sorted input is a compact building block. Once it is in your long-term memory, you can assemble it into harder problems without thinking about the mechanics.

Related posts

• Container With Most Water - Opposite-end two-pointer convergence, another way sorted structure drives pointer decisions
• 3Sum Closest - Uses converging two pointers as its inner loop after sorting the array
• Two Sum II - The classic converging two-pointer problem on sorted input