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 max_distance = 0 to track the maximum distance found.

2. Iterate through nums1: For each element nums1[i]:

3. Binary search in nums2: For each nums1[i], we search in nums2 starting from index i to find the first position where nums2[j] < nums1[i]. The last valid position is then j - 1.

4. Apply the template: Using the standard binary search template:

   left, right = i, len(nums2) - 1
   first_true_index = -1
   
   while left <= right:
       mid = (left + right) // 2
       if nums2[mid] < nums1[i]:  # feasible condition
           first_true_index = mid
           right = mid - 1
       else:
           left = mid + 1

   • The feasible condition nums2[mid] < nums1[i] finds the first index where the pair becomes invalid
   • If first_true_index != -1, the last valid j is first_true_index - 1
   • If first_true_index == -1, all positions from i to end are valid, so last valid j is len(nums2) - 1

5. Calculate distance and update maximum:

   • Compute the distance as j - i where j is the last valid position
   • Update max_distance with the maximum of current max_distance and the new distance
   • Only update if j >= i (valid pair condition)

6. 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(1) as we only use a constant amount of extra space.

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

• max_distance = 0

Step 2: Process each element in nums1

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

• Search range: left = 0, right = 4
• Find first j where nums2[j] < 10
• Binary search:
  • mid = 2: nums2[2] = 8 < 10 ✓ → first_true_index = 2, right = 1
  • mid = 0: nums2[0] = 12 >= 10 → left = 1
  • mid = 1: nums2[1] = 11 >= 10 → left = 2
  • Loop ends with first_true_index = 2
• Last valid j = first_true_index - 1 = 1
• Verify: nums2[1] = 11 >= 10 ✓
• Distance = 1 - 0 = 1
• Update max_distance = max(0, 1) = 1

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

• Search range: left = 1, right = 4
• Find first j where nums2[j] < 8
• Binary search:
  • mid = 2: nums2[2] = 8 >= 8 → left = 3
  • mid = 3: nums2[3] = 5 < 8 ✓ → first_true_index = 3, right = 2
  • Loop ends with first_true_index = 3
• Last valid j = first_true_index - 1 = 2
• Verify: nums2[2] = 8 >= 8 ✓
• Distance = 2 - 1 = 1
• Update max_distance = max(1, 1) = 1

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

• Search range: left = 2, right = 4
• Find first j where nums2[j] < 2
• Binary search:
  • mid = 3: nums2[3] = 5 >= 2 → left = 4
  • mid = 4: nums2[4] = 2 >= 2 → left = 5
  • Loop ends with first_true_index = -1 (no j where nums2[j] < 2)
• All positions valid, so last valid j = len(nums2) - 1 = 4
• Verify: nums2[4] = 2 >= 2 ✓
• Distance = 4 - 2 = 2
• Update max_distance = 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 template efficiently finds the first invalid position, from which we derive the last valid position.

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 in nums2 (which takes O(log n) time per search)
• Therefore, the total time complexity is O(m × log n)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables like left, right, mid, first_true_index, last_valid_j, and max_distance, regardless of the input size.

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

Common Pitfalls

1. Using the wrong binary search template variant

A common mistake is using while left < right with right = mid instead of the standard template.

Wrong approach:

while left < right:
    mid = (left + right) // 2
    if nums2[mid] < value:
        right = mid
    else:
        left = mid + 1
return left - 1  # Error-prone calculation

Correct approach (using the standard template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if nums2[mid] < value:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
# last_valid_j = first_true_index - 1 if found, else n2 - 1

2. Forgetting to handle when no invalid position exists

When all positions from i to the end are valid (all nums2[j] >= nums1[i]), first_true_index remains -1.

Pitfall:

# Wrong: directly using first_true_index - 1
last_valid_j = first_true_index - 1  # Returns -2 when first_true_index is -1!

Solution: Always check if first_true_index == -1:

if first_true_index == -1:
    last_valid_j = n2 - 1  # All positions valid
else:
    last_valid_j = first_true_index - 1

3. Not validating that j >= i before calculating distance

The constraint requires i <= j, but after binary search, last_valid_j might be less than i.

Pitfall:

# Wrong: not checking if j >= i
max_distance = max(max_distance, last_valid_j - i)  # Could add negative distance

Solution: Always check the valid pair condition:

if last_valid_j >= i:
    max_distance = max(max_distance, last_valid_j - i)

4. Starting the search range from 0 instead of i

The problem requires i <= j, so the search should start from index i, not 0.

Pitfall:

# Wrong: searching from index 0
left, right = 0, n2 - 1  # May find j < i

Solution: Start from index i:

left, right = i, n2 - 1  # Ensures j >= i