April 19Medium

Maximum distance between a pair of values

Topics: Array
Two Pointers
Binary Search

Problem

You are given two non-increasing 0-indexed integer arrays nums1 and nums2. A pair of indices (i, j), where 0 <= i < nums1.length and 0 <= j < nums2.length is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i. Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

Solution

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        def bin_search(i):
            l, r = i, len(nums2)
            while l < r:
                m = (l+r)//2
                if nums2[m] >= nums1[i]:
                    l = m+1
                else:
                    r = m
            return l - 1

        res = 0
        for i in range(min(len(nums2), len(nums1))):
            if nums1[i] > nums2[i]:
                continue
            j = bin_search(i)
            res = max(res, j - i)

        return res