1855. Maximum Distance Between a Pair of Values

MediumView on LeetCode

Time: O(n + m)

Space: O(1)

Intuition

Maximum distance between indices i < j such that nums1[i] >= nums2[j]. Binary search or two pointers.

Algorithm

1For each i: binary search for rightmost j where nums2[j] <= nums1[i]. Answer = max(j-i).
2Or: two pointers from left. Track j for each valid i.

Common Pitfalls

•nums1 and nums2 are not necessarily sorted by value. Binary search may not directly apply unless we use monotonic properties.

1855.cs

// Approach: Two pointers on the two non-increasing arrays.
// Advance i (left pointer in nums1) when nums1[i] > nums2[j] — the current pair is invalid.
// Otherwise j - i is a valid distance; record it and advance j to try a larger distance.
// Because both arrays are non-increasing, advancing i can only make pairs tighter,
// and advancing j can only make the distance wider, so the greedy order is correct.
// Time: O(n + m) Space: O(1)
public class Solution
{
    public int MaxDistance(int[] nums1, int[] nums2)
    {
        int ans = 0;
        int i = 0;
        int j = 0;

        while (i < nums1.Length && j < nums2.Length)
        {
            if (nums1[i] > nums2[j])
                ++i;
            else
                ans = Math.Max(ans, j++ - i);
        }

        return ans;
    }
}

Was this solution helpful?