Solution Approach

The solution uses sorting and the binary search template to find the optimal replacement.

Step 1: Initial Setup

• Create a sorted copy of nums1 for binary searching
• Calculate the initial absolute sum difference

Step 2: Binary Search Template for Finding Closest Element

We use the template to find the first element >= target:

def find_first_ge(target: int) -> int:
    left, right = 0, n - 1
    first_true_index = -1

    while left <= right:
        mid = (left + right) // 2
        if sorted_nums1[mid] >= target:
            first_true_index = mid
            right = mid - 1
        else:
            left = mid + 1

    return first_true_index

The feasibility condition sorted_nums1[mid] >= target creates the pattern:

• Elements before target: return false
• Elements at or after target: return true

Step 3: Find Optimal Replacement for Each Position

For each pair (num1, num2):

1. Calculate the current difference: current_diff = abs(num1 - num2)
2. Use find_first_ge(num2) to find the first element >= num2
3. Check two candidates for the closest value:
   • If idx != -1: check sorted_nums1[idx] (first element >= num2)
   • If idx == -1: all elements < num2, check the last element
   • If idx > 0: check sorted_nums1[idx-1] (element just before)
4. Track the maximum possible reduction

Step 4: Calculate Final Answer

Return (total_diff - max_reduction + MOD) % MOD

Time Complexity: O(n log n) for sorting and n binary searches Space Complexity: O(n) for storing the sorted copy of nums1

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• nums1 = [5, 10, 3]
• nums2 = [7, 2, 8]

Step 1: Initial Setup

• Create sorted copy: nums = [3, 5, 10]
• Calculate initial sum:
  • |5-7| + |10-2| + |3-8| = 2 + 8 + 5 = 15
• Initialize mx = 0 (maximum reduction tracker)

Step 2: Find Optimal Replacement for Each Position

Position 0: (a=5, b=7)

• Current difference: d1 = |5-7| = 2
• Find closest value to 7 in sorted nums = [3, 5, 10]:
  • bisect_left([3, 5, 10], 7) returns index 2
  • Check candidate at index 2: nums[2] = 10, difference = |10-7| = 3
  • Check candidate at index 1: nums[1] = 5, difference = |5-7| = 2
• Best replacement gives d2 = 2
• Reduction: d1 - d2 = 2 - 2 = 0
• Update: mx = max(0, 0) = 0

Position 1: (a=10, b=2)

• Current difference: d1 = |10-2| = 8
• Find closest value to 2 in sorted nums = [3, 5, 10]:
  • bisect_left([3, 5, 10], 2) returns index 0
  • Check candidate at index 0: nums[0] = 3, difference = |3-2| = 1
  • No candidate before index 0
• Best replacement gives d2 = 1
• Reduction: d1 - d2 = 8 - 1 = 7
• Update: mx = max(0, 7) = 7

Position 2: (a=3, b=8)

• Current difference: d1 = |3-8| = 5
• Find closest value to 8 in sorted nums = [3, 5, 10]:
  • bisect_left([3, 5, 10], 8) returns index 2
  • Check candidate at index 2: nums[2] = 10, difference = |10-8| = 2
  • Check candidate at index 1: nums[1] = 5, difference = |5-8| = 3
• Best replacement gives d2 = 2
• Reduction: d1 - d2 = 5 - 2 = 3
• Update: mx = max(7, 3) = 7

Step 3: Calculate Final Answer

• Original sum: 15
• Maximum reduction: 7
• Final answer: 15 - 7 = 8

The optimal replacement is at position 1, where we replace nums1[1] = 10 with 3 (from nums1[2]), giving us the array [5, 3, 3] and reducing the total sum from 15 to 8.

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums1.

• Sorting nums1 takes O(n × log n) time
• Computing the initial sum takes O(n) time
• The main loop iterates n times, and for each iteration:
  • bisect_left performs binary search on the sorted array, taking O(log n) time
  • All other operations inside the loop take O(1) time
• Therefore, the loop contributes O(n × log n) time
• Overall time complexity: O(n × log n) + O(n) + O(n × log n) = O(n × log n)

The space complexity is O(n).

• Creating a sorted copy of nums1 requires O(n) additional space
• All other variables (s, mx, d1, d2, i) use O(1) space
• Overall space complexity: O(n)

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

Common Pitfalls

1. Using Wrong Binary Search Template Variant

Pitfall: Using while left < right with right = mid instead of the standard template.

Wrong Implementation:

while left < right:
    mid = (left + right) >> 1
    if nums[mid] >= target:
        right = mid
    else:
        left = mid + 1
return left

Correct Implementation (using template):

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if sorted_nums1[mid] >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

2. Modulo Operation Handling Error

Pitfall: Simply doing (total_diff - max_reduction) % MOD can produce issues.

Solution: Add MOD before taking the modulo:

return (total_diff - max_reduction + MOD) % MOD

3. Not Checking Both Neighbors in Binary Search

Pitfall: Only checking one candidate value after binary search, missing the optimal replacement.

Example:

• sorted_nums1 = [1, 5, 10] and num2 = 6
• Template returns first_true_index = 2 (element 10 >= 6)
• Only checking index 2 gives difference 4
• But checking index 1 gives difference 1 (better!)

Solution: Check both first_true_index and first_true_index - 1 when they exist.

4. Handling first_true_index = -1

Pitfall: Not handling the case when all elements are less than the target.

Solution: When first_true_index == -1, the closest element must be the last one:

if idx == -1:
    min_possible_diff = min(min_possible_diff, abs(sorted_nums1[n - 1] - num2))