Problem Statement in English

You’re given two non-increasing integer arrays nums1 and nums2. A pair of indices (i, j) is valid if i < j, 0 <= i < nums1.length, 0 <= j < nums2.length, 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.

Approach

Since the arrays are non-increasing, we can use binary search to find the rightmost index j in nums2 such that nums2[j] >= nums1[i] for each index i in nums1. We can then calculate the distance j - i and keep track of the maximum distance found.

I want to use the bisect module, and bisect expects that the list is sorted. However the input list is sorted in reverse. We need to use the classic custom key function to make it work.

So in the comparator function we negate the values to make the descending order list behave like an ascending order list. Next up, we need to make sure that the search starts from index i in nums2 to ensure that j > i. And since we’re negating elements of the list we also negate the target value.

Solution in Python


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

        for i, val in enumerate(nums1):
            idx = bisect_right(nums2, -val, lo=i, key=lambda x: -x)
            
            j = idx - 1
            if j >= i:
                res = max(res, j - i)
                
        return res

Complexity

  • Time: $O(n \log m)$
    Since we iterate through nums1 and for each element, we perform a binary search on nums2.

  • Space: $O(1)$
    Since we are using only constant space.

Mistakes I Made

I messed up using bisect_right with a custom key function.

And we are done.