Minimum Absolute Sum Difference: Binary Search for Best Replacement

LeetCode 1818. Minimum Absolute Sum Difference gives you two arrays nums1 and nums2 of the same length. The absolute sum difference is the sum of |nums1[i] - nums2[i]| for every index. You are allowed to replace at most one element of nums1 with any other element already in nums1. Your goal is to minimize the absolute sum difference after that single replacement, returning the result modulo 10^9 + 7.

Example 1: nums1 = [1,7,5], nums2 = [2,3,5]. The original absolute sum difference is |1-2| + |7-3| + |5-5| = 1 + 4 + 0 = 5. If you replace nums1[1] = 7 with 5, the sum becomes |1-2| + |5-3| + |5-5| = 1 + 2 + 0 = 3. Output: 3.

Example 2: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]. Every difference is already 0, so no replacement helps. Output: 0.

The approach

The key insight is that you only get one replacement, so you want to find the position where a replacement yields the biggest reduction in absolute difference. For each index i, you want to find the element in nums1 that is closest to nums2[i], because replacing nums1[i] with that closest value would minimize |replacement - nums2[i]|.

Here is the plan:

1. Compute the original total: sum of |nums1[i] - nums2[i]| across all indices.
2. Sort a copy of nums1. Call it sorted_nums1.
3. For each index i, use binary search on sorted_nums1 to find the value closest to nums2[i]. Compute the new difference |closest - nums2[i]|, then compute the reduction as original_diff[i] - new_diff. Track the maximum reduction seen.
4. Return (total - max_reduction) % (10^9 + 7).

The binary search at each index runs in O(log n), and you do it for all n positions, so the overall time is O(n log n).

The code

from bisect import bisect_left

def minAbsoluteSumDiff(nums1, nums2):
    MOD = 10**9 + 7
    n = len(nums1)
    sorted_nums1 = sorted(nums1)
    total = 0
    max_reduction = 0

    for i in range(n):
        original_diff = abs(nums1[i] - nums2[i])
        total += original_diff

        if original_diff == 0:
            continue

        pos = bisect_left(sorted_nums1, nums2[i])

        best_new_diff = original_diff
        if pos < n:
            best_new_diff = min(best_new_diff, abs(sorted_nums1[pos] - nums2[i]))
        if pos > 0:
            best_new_diff = min(best_new_diff, abs(sorted_nums1[pos - 1] - nums2[i]))

        max_reduction = max(max_reduction, original_diff - best_new_diff)

    return (total - max_reduction) % MOD

Here is what happens step by step with nums1 = [1, 7, 5] and nums2 = [2, 3, 5]:

1. Sort a copy: sorted_nums1 = [1, 5, 7].
2. Compute original total: |1-2| + |7-3| + |5-5| = 1 + 4 + 0 = 5.
3. At index 0, nums2[0] = 2. Binary search finds insertion point 1. Check sorted_nums1[1] = 5 (diff 3) and sorted_nums1[0] = 1 (diff 1). Best new diff is 1, reduction is 1 - 1 = 0.
4. At index 1, nums2[1] = 3. Binary search finds insertion point 1. Check sorted_nums1[1] = 5 (diff 2) and sorted_nums1[0] = 1 (diff 2). Best new diff is 2, reduction is 4 - 2 = 2.
5. At index 2, original diff is 0, so skip.
6. Maximum reduction is 2. Answer: (5 - 2) % (10^9 + 7) = 3.

Visual walkthrough

Each step below shows how the algorithm processes the example, from computing the baseline total to selecting the best replacement.

The algorithm never actually performs the replacement. It just computes what the improvement would be for each index and picks the best one. This makes the logic clean and avoids mutating the original array.

Complexity analysis

Sorting the copy of nums1 takes O(n log n). The loop runs n iterations, each doing an O(log n) binary search, for another O(n log n). The total time is O(n log n). Space is O(n) for the sorted copy.

Building blocks

Binary search for closest value

When you need the element in a sorted array closest to a target, use bisect_left to find the insertion point, then compare the candidate at that index with the one just before it. This two-candidate check is a recurring pattern in problems where you need nearest neighbors in sorted data.

Greedy optimization with sorting

Sorting unlocks efficient lookups. Here, you sort once and then query many times, which is a classic tradeoff: spend O(n log n) upfront to get O(log n) per query. Whenever a brute-force approach checks all elements for each position, consider whether sorting plus binary search can cut that inner loop down.

Edge cases

All elements identical: If nums1 and nums2 are identical, every difference is 0 and max_reduction stays at 0. The answer is 0 with no replacement needed.

Replacement makes no improvement: Sometimes the best replacement for every index matches the original value. In that case max_reduction is 0 and you return the original total modulo 10^9 + 7.

Large arrays with large values: Since values can be up to 10^5 and array length up to 10^5, the total sum can exceed standard 32-bit integer limits. Python handles big integers natively, but in other languages you should use 64-bit integers for the running total.

Single element arrays: When n = 1, there is only one position and one value to choose from. The replacement is nums1[0] itself, so the answer is |nums1[0] - nums2[0]| % (10^9 + 7).

From understanding to recall

This problem combines two foundational patterns: sorting for efficient lookup and binary search for closest value. To build lasting recall, practice these building blocks separately. Sort-then-search shows up in problems ranging from two-sum variants to interval scheduling. The "check both neighbors at the insertion point" technique for finding the closest value is a small but critical detail that trips people up under pressure. Drilling it with spaced repetition turns it into an automatic reflex rather than something you have to re-derive each time.

Related posts

• Find First and Last Position of Element in Sorted Array - Binary search in sorted arrays
• Search Insert Position - Finding insertion points with binary search
• Kth Largest Element in an Array - Sorting-based optimization