Minimum Absolute Sum Difference - Video Solutions
LeetCode 1818. Minimum Absolute Sum Difference | Medium | 🏆 Weekly Contest 235 | Algorithm Explained
Minimum Absolute Sum Difference - Video Solution
Watch 9 video solutions for Minimum Absolute Sum Difference, a medium level problem involving Array, Binary Search, Sorting. This walkthrough by Cherry Coding [IIT-G] has 9,243 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two positive integer arrays nums1 and nums2, both of length n.
The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).
You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.
Return the minimum absolute sum difference after replacing at most one element in the array nums1. Since the answer may be large, return it modulo 109 + 7.
|x| is defined as:
xifx >= 0, or-xifx < 0.
Example 1:
Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: There are two possible optimal solutions:
- Replace the second element with the first: [1,7,5] => [1,1,5], or
- Replace the second element with the third: [1,7,5] => [1,5,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.
Example 2:
Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10] Output: 0 Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an absolute sum difference of 0.
Example 3:
Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7].
This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20
Constraints:
n == nums1.lengthn == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 105
Approach Overview
Problem Overview: You are given two arrays nums1 and nums2 of equal length. The cost is the sum of |nums1[i] - nums2[i]| for every index. You may replace at most one element in nums1 with any other value already present in nums1. The goal is to minimize the total absolute difference.
Approach 1: Brute Force Replacement (O(n^2) time, O(1) space)
First compute the baseline sum of |nums1[i] - nums2[i]|. Then try improving it by replacing nums1[i] with every possible value from nums1. For each index i, iterate through the entire array and calculate the new difference if that value were used instead. Track the maximum reduction achievable from a single replacement. This approach directly simulates the operation but requires nested iteration over the array, resulting in O(n^2) time. It works for small inputs and clearly demonstrates the optimization opportunity.
Approach 2: Sorted Array + Binary Search (O(n log n) time, O(n) space)
The key observation: when replacing nums1[i], the best candidate is the value in nums1 closest to nums2[i]. Instead of scanning the entire array, sort a copy of nums1. For each index i, use binary search to locate the closest value to nums2[i] in the sorted array. Compare both the insertion position and its neighbor to find the minimum possible difference. Compute how much this replacement would reduce the current absolute difference, and track the maximum improvement. Finally subtract that improvement from the baseline sum. Sorting enables fast lookups, reducing the total complexity to O(n log n). This technique combines Array traversal with Binary Search on a sorted structure.
Recommended for interviews: The binary search optimization is the expected solution. Interviewers want to see you recognize that only the closest value to nums2[i] matters, which allows replacing a quadratic scan with a logarithmic lookup. Starting with the brute force approach shows you understand the operation, but transitioning to a sorted array and binary search demonstrates strong algorithmic thinking.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Replacement | O(n^2) | O(1) | Useful for understanding the replacement logic or when input size is very small |
| Sorted Array + Binary Search | O(n log n) | O(n) | General case and interview solution where fast nearest-value lookup is required |