Problem Description

You are given two integer arrays nums1 and nums2 that are both non-increasing (sorted in descending order or staying the same).

Your task is to find a pair of indices (i, j) where:

• i is an index from nums1 (where 0 <= i < nums1.length)
• j is an index from nums2 (where 0 <= j < nums2.length)

For a pair (i, j) to be valid, it must satisfy two conditions:

1. i <= j (the index in nums1 cannot be greater than the index in nums2)
2. nums1[i] <= nums2[j] (the value at index i in nums1 must be less than or equal to the value at index j in nums2)

The distance of a valid pair (i, j) is calculated as j - i.

You need to find the maximum distance among all valid pairs. If no valid pairs exist, return 0.

Example of non-increasing array: An array like [5, 4, 4, 2, 1] is non-increasing because each element is less than or equal to the previous one.

The solution uses binary search to efficiently find valid pairs. For each element in nums1 at index i, it searches for the rightmost position in nums2 (starting from index i) where a valid pair can be formed, maximizing the distance j - i.

Intuition

Since both arrays are non-increasing (sorted in descending order), we can leverage this property to efficiently find valid pairs.

For each element nums1[i], we want to find the farthest valid index j in nums2 such that nums1[i] <= nums2[j] and i <= j. To maximize the distance j - i, we need to find the largest possible j.

Because nums2 is non-increasing, once we find a position where nums1[i] > nums2[j], all positions after j will also fail the condition nums1[i] <= nums2[j]. This monotonic property makes binary search a perfect fit.

The key insight is that for each nums1[i], we're looking for the last (rightmost) position in nums2 where the value is still greater than or equal to nums1[i]. Since nums2 is in descending order, all valid positions form a continuous range from the start of the search range up to some point.

To use binary search effectively with bisect_left, the solution cleverly reverses nums2. After reversing, nums2 becomes non-decreasing (ascending), which allows us to use bisect_left to find where nums1[i] would fit. The position found corresponds to the first element that is greater than or equal to nums1[i] in the reversed array, which translates back to the last valid position in the original array.

By iterating through each element in nums1 and finding the optimal pairing in nums2 using binary search, we achieve an efficient O(m * log n) solution instead of the brute force O(m * n) approach.

Learn more about Two Pointers and Binary Search patterns.

Solution Approach

The solution uses binary search to efficiently find the maximum distance between valid pairs.

Step-by-step Implementation:

1. Initialize the answer: Start with ans = 0 to track the maximum distance found.

2. Reverse nums2: The solution reverses nums2 using nums2[::-1]. This transforms the non-increasing array into a non-decreasing array, making it suitable for using Python's bisect_left function.

   • Original nums2: [5, 4, 2, 1] (non-increasing)
   • Reversed nums2: [1, 2, 4, 5] (non-decreasing)

3. Iterate through nums1: For each element nums1[i] with value v:

4. Binary search in reversed nums2: Use bisect_left(nums2, v) on the reversed array to find the leftmost position where v could be inserted while maintaining sorted order.

   • bisect_left returns the index where v should be inserted in the reversed array
   • This corresponds to the first element that is greater than or equal to v in the reversed array

5. Convert back to original index: Calculate the actual index j in the original nums2:

   j = len(nums2) - bisect_left(nums2, v) - 1

   • Since the array was reversed, we need to map the position back to the original array
   • This gives us the last position in the original nums2 where nums2[j] >= nums1[i]

6. Calculate distance and update maximum:

   • Compute the distance as j - i
   • Update ans with the maximum of current ans and the new distance
   • Note: The solution doesn't explicitly check i <= j because negative distances will never be the maximum

7. Return the result: After checking all elements in nums1, return the maximum distance found.

Time Complexity: O(m * log n) where m is the length of nums1 and n is the length of nums2. We perform a binary search (O(log n)) for each element in nums1.

Space Complexity: O(n) for creating the reversed copy of nums2.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

• nums1 = [10, 8, 2] (non-increasing)
• nums2 = [12, 11, 8, 5, 2] (non-increasing)

Step 1: Initialize and Reverse

• ans = 0
• Reverse nums2 to get [2, 5, 8, 11, 12] (now non-decreasing)

Step 2: Process each element in nums1

For i = 0, nums1[0] = 10:

• Use bisect_left([2, 5, 8, 11, 12], 10) → returns index 3
  • This means 10 would be inserted at position 3 in the reversed array
• Convert back to original index: j = 5 - 3 - 1 = 1
• In original nums2, position 1 has value 11, and indeed 10 ≤ 11 ✓
• Distance = 1 - 0 = 1
• Update ans = max(0, 1) = 1

For i = 1, nums1[1] = 8:

• Use bisect_left([2, 5, 8, 11, 12], 8) → returns index 2
  • Value 8 exists, so it returns the position of the first 8
• Convert back to original index: j = 5 - 2 - 1 = 2
• In original nums2, position 2 has value 8, and indeed 8 ≤ 8 ✓
• Distance = 2 - 1 = 1
• Update ans = max(1, 1) = 1

For i = 2, nums1[2] = 2:

• Use bisect_left([2, 5, 8, 11, 12], 2) → returns index 0
  • Value 2 exists at the beginning of reversed array
• Convert back to original index: j = 5 - 0 - 1 = 4
• In original nums2, position 4 has value 2, and indeed 2 ≤ 2 ✓
• Distance = 4 - 2 = 2
• Update ans = max(1, 2) = 2

Result: The maximum distance is 2, achieved by the pair (i=2, j=4) where nums1[2] = 2 and nums2[4] = 2.

The binary search efficiently finds the rightmost valid position in nums2 for each element in nums1, avoiding the need to check every possible pair.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × log n), where m is the length of nums1 and n is the length of nums2. This is because:

• The code iterates through each element in nums1 (which takes O(m) time)
• For each element, it performs a binary search using bisect_left on the reversed nums2 array (which takes O(log n) time per search)
• Therefore, the total time complexity is O(m × log n)

The space complexity is O(n), not O(1) as stated in the reference answer. This is because:

• The line nums2 = nums2[::-1] creates a reversed copy of nums2, which requires O(n) additional space
• The other variables (ans, i, v, j) only use constant space

Note: The reference answer's space complexity of O(1) would be correct if the code modified nums2 in-place or used a different approach that didn't create a copy of the array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly handling the index mapping after reversal

When reversing nums2 and using binary search, a common mistake is incorrectly converting the position back to the original index. The formula j = len(nums2) - position_in_reversed - 1 can be confusing.

Why this happens: After reversing, bisect_left returns the position where the value would be inserted in the reversed array. This position needs to be mapped back to find the rightmost valid index in the original array.

Example of the mistake:

# Wrong: forgetting the -1
j = len(nums2) - position_in_reversed  # This gives an off-by-one error

# Wrong: using bisect_right instead
position = bisect_right(reversed_nums2, value)
j = len(nums2) - position - 1  # This may miss valid pairs

Solution: Always remember that for a reversed array of length n, index i in the reversed array corresponds to index (n-1-i) in the original array.

2. Not checking if j >= i before calculating distance

The current solution calculates j - i for all cases and relies on max() to filter out negative distances. However, this can be inefficient and unclear.

Better approach:

for i, value in enumerate(nums1):
    position_in_reversed = bisect_left(reversed_nums2, value)
    j = len(nums2) - position_in_reversed - 1
  
    # Only update if j >= i (valid pair condition)
    if j >= i:
        max_distance = max(max_distance, j - i)

3. Misunderstanding bisect_left behavior with duplicates

When nums2 contains duplicate values, bisect_left finds the leftmost position in the reversed array. This correctly translates to the rightmost position in the original array, maximizing the distance.

Example scenario:

• Original nums2 = [5, 3, 3, 3, 1]
• Reversed nums2 = [1, 3, 3, 3, 5]
• Searching for value 3: bisect_left returns index 1
• This maps to index 3 in the original array (the rightmost 3)

Pitfall: Using bisect_right instead would give a different position and potentially miss the maximum distance.

4. Forgetting edge cases

The solution doesn't explicitly handle edge cases like empty arrays or when all pairs are invalid.

Improved version with edge case handling:

def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
    if not nums1 or not nums2:
        return 0
  
    max_distance = 0
    reversed_nums2 = nums2[::-1]
  
    for i, value in enumerate(nums1):
        # Early termination: if i is already beyond nums2's length
        if i >= len(nums2):
            break
          
        position_in_reversed = bisect_left(reversed_nums2, value)
        j = len(nums2) - position_in_reversed - 1
      
        if j >= i:
            max_distance = max(max_distance, j - i)
  
    return max_distance