1855. Maximum Distance Between a Pair of Values

Intuition

Both arrays are sorted in descending order. Use two pointers: as nums1[i] decreases (increasing i), we can extend j further to find larger distances.

Solution

Two Pointers

i, j = 0, 0
max_dist = 0

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

Why This Works

• If nums1[i] <= nums2[j]: valid pair, try to extend j for larger distance
• If nums1[i] > nums2[j]: need smaller nums1 value, so increment i
• Since arrays are non-increasing:
  • Moving i right → nums1[i] decreases → more likely to satisfy condition
  • Moving j right → nums2[j] decreases → condition may break

Constraint i <= j

The algorithm naturally maintains i <= j because:

• When valid (i <= j maintained), we increment j
• When invalid and i increments past j, the condition will soon become valid again (or we exhaust arrays)

For safety, we can add: if i > j after incrementing i, skip.

Complexity

• Time: O(n + m)
• Space: O(1)

Edge Cases

• No valid pairs → return 0
• All pairs valid → return n2 - 1
• Single element arrays

from typing import List


class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        """
        1855. Maximum Distance Between a Pair of Values
        Time: O(n + m)
        Space: O(1)
        """
        n1, n2 = len(nums1), len(nums2)
        i, j = 0, 0
        max_dist = 0

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

        return max_dist

/**
 * 1855. Maximum Distance Between a Pair of Values
 * Time: O(n + m)
 * Space: O(1)
 */
class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int i = 0, j = 0;
        int maxDist = 0;

        while (i < n1 && j < n2) {
            if (nums1[i] <= nums2[j]) {
                maxDist = Math.max(maxDist, j - i);
                j++;
            } else {
                i++;
            }
        }

        return maxDist;
    }
}