Problem Description

You have two positive integer arrays nums1 and nums2, both with the same length n.

The absolute sum difference between these arrays is calculated by summing up |nums1[i] - nums2[i]| for all indices i from 0 to n-1.

Your task is to minimize this absolute sum difference by replacing at most one element in nums1. You can replace any element in nums1 with any other element that already exists in nums1.

For example, if nums1 = [1, 7, 5] and nums2 = [2, 3, 5]:

• The original absolute sum difference is |1-2| + |7-3| + |5-5| = 1 + 4 + 0 = 5
• You could replace nums1[1] = 7 with nums1[0] = 1 to get [1, 1, 5]
• The new absolute sum difference would be |1-2| + |1-3| + |5-5| = 1 + 2 + 0 = 3

Return the minimum possible absolute sum difference after performing at most one replacement. Since the answer might be very large, return it modulo 10^9 + 7.

The absolute value |x| is defined as:

• x if x >= 0
• -x if x < 0

Intuition

The key insight is that we want to find the single replacement that gives us the maximum reduction in the total sum.

Let's think about what happens when we replace nums1[i] with some other value from nums1. The only term in the total sum that changes is |nums1[i] - nums2[i]|. If we replace nums1[i] with a different value x (where x must already exist in nums1), this term becomes |x - nums2[i]|.

The reduction we get from this replacement is: original difference - new difference = |nums1[i] - nums2[i]| - |x - nums2[i]|

To maximize our reduction, we want to find the value x in nums1 that minimizes |x - nums2[i]|. In other words, we want to find the element in nums1 that is closest to nums2[i].

This naturally leads us to a binary search approach:

1. First, calculate the total absolute sum difference without any replacements
2. For each position i, find the element in nums1 that is closest to nums2[i]
3. Calculate how much we can reduce the sum by making this replacement
4. Track the maximum possible reduction across all positions
5. Subtract this maximum reduction from the original sum

To efficiently find the closest element, we can sort a copy of nums1 and use binary search. For each nums2[i], we use bisect_left to find where nums2[i] would fit in the sorted array. The closest element must be either at this position or the position just before it.

The final answer is (original_sum - max_reduction) % mod.

Learn more about Binary Search and Sorting patterns.

Solution Approach

The solution follows a sorting and binary search strategy to find the optimal replacement:

Step 1: Initial Setup

• Create a sorted copy of nums1 called nums for binary searching
• Calculate the initial absolute sum difference: s = sum(abs(a - b) for a, b in zip(nums1, nums2)) % mod
• Initialize mx = 0 to track the maximum reduction we can achieve

Step 2: Find Optimal Replacement for Each Position

For each pair (a, b) from (nums1[i], nums2[i]):

1. Calculate the current difference: d1 = abs(a - b)

2. Find the best replacement value from nums1 that would minimize the difference with b:

   • Use bisect_left(nums, b) to find the insertion position i where b would fit in the sorted array
   • Check two candidates for the closest value:
     • If i < len(nums): check nums[i] (the element at or just after b)
     • If i > 0: check nums[i-1] (the element just before b)
   • Calculate d2 as the minimum absolute difference using the best replacement

3. Update the maximum reduction: mx = max(mx, d1 - d2)

   • d1 - d2 represents how much we can reduce the sum by replacing a with the optimal value

Step 3: Calculate Final Answer

Return (s - mx + mod) % mod

• We subtract the maximum reduction from the original sum
• Add mod before taking modulo to handle potential negative values correctly

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

The binary search is crucial here because it allows us to efficiently find the closest element in O(log n) time for each position, rather than checking all elements which would take O(n²) time overall.

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.

Solution Implementation

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. Modulo Operation Handling Error

Pitfall: A common mistake is incorrectly handling the modulo operation when calculating the final result. Simply doing (total_diff - max_reduction) % MOD can produce incorrect results when max_reduction > total_diff.

Why it happens: When we subtract max_reduction from total_diff, we might get a negative number. In Python, the modulo of a negative number can produce unexpected results in the context of this problem.

Example scenario:

• If total_diff = 5 and max_reduction = 7
• Direct calculation: (5 - 7) % MOD = -2 % MOD = 1000000005 (in Python)
• But we want the result to be equivalent to a positive difference

Solution: Add MOD before taking the modulo to ensure a positive result:

return (total_diff - max_reduction + MOD) % MOD

2. Integer Overflow in Initial Sum Calculation

Pitfall: Forgetting to apply modulo during the initial sum calculation, which could lead to integer overflow in languages with fixed integer sizes (though Python handles big integers automatically).

Why it happens: The sum of absolute differences across all elements could exceed the modulo value significantly before we apply the modulo operation.

Solution: Apply modulo immediately after calculating the initial sum:

total_diff = sum(abs(num1 - num2) for num1, num2 in zip(nums1, nums2)) % MOD

3. Not Checking Both Neighbors in Binary Search

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

Why it happens: bisect_left returns the leftmost insertion position. The closest value to num2 could be either at this position or at the position just before it.

Example:

• sorted_nums1 = [1, 5, 10] and num2 = 6
• bisect_left returns index 2 (position for inserting 6)
• Only checking index 2 gives us 10 with difference |10-6| = 4
• But checking index 1 gives us 5 with difference |5-6| = 1 (better!)

Solution: Always check both candidates when they exist:

if insertion_point < len(sorted_nums1):
    min_possible_diff = min(min_possible_diff, abs(sorted_nums1[insertion_point] - num2))

if insertion_point > 0:
    min_possible_diff = min(min_possible_diff, abs(sorted_nums1[insertion_point - 1] - num2))

4. Forgetting Edge Cases with Empty or Single Element Arrays

Pitfall: Not handling cases where the insertion point is at the boundaries (0 or len(array)).

Solution: The code correctly uses conditional checks (if insertion_point < len(sorted_nums1) and if insertion_point > 0) to avoid index out of bounds errors.