Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Both arrays are nonincreasing. If nums1[i] exceeds nums2[j], moving j farther right cannot help, so i must advance toward a smaller first-array value. When a pair is valid, increasing j is the way to seek a larger distance.

Approach

Start both pointers at zero. For i <= j with nums1[i] <= nums2[j], record j - i and advance j. If the value inequality fails, advance i. If only the index-order requirement fails, advance j until it can catch up. Stop when either pointer exhausts its array and return the greatest recorded distance, initially zero.

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

        while i < n and j < m:
            if i <= j and nums1[i] <= nums2[j]:
                res = max(res, j - i)
                j += 1 # try larger range
            elif nums1[i] > nums2[j]: i += 1 # try smaller n1
            elif i > j: j += 1 # try larger j
        
        return res

Complexity analysis

Let n = nums1.length and m = nums2.length. Time: O(n + m), because neither pointer moves backward. Auxiliary space: O(1).