Skip to main content
Talentd

Minimum Absolute Sum Difference - Solution & Explanation

MediumArrayBinary SearchSortingOrdered Set14 min readAsked at: Uber
Practice this problem

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:

  • x if x >= 0, or
  • -x if x < 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.length
  • n == nums2.length
  • 1 <= n <= 105
  • 1 <= 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.

Approach 1: Brute Force Approach

The naive brute force approach involves iterating through each element of the nums1 array and trying to replace it with every other element from the array. For each replacement, compute the absolute sum difference and keep track of the minimum difference encountered. While simple, this approach is inefficient due to its O(n^2) time complexity, which can be impractical for large input sizes.

This solution iterates through each index of nums1 and considers replacing the value with every other potential value from nums1. After each potential replacement, it recalculates the whole sum of absolute differences.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time complexity: O(n^2)
Space complexity: O(1) (ignoring input size)

Try this approach in the editor →

Approach 2: Optimized Approach using Binary Search

This approach aims to minimize the maximum individual absolute difference by using binary search. The idea is to pre-sort nums1 and for each element in nums2, find the closest element in nums1 to minimize the absolute difference. Sorting and using a binary search allows this approach to efficiently handle large input sizes, bringing down the time complexity from O(n^2) to O(n log n).

This implementation first calculates the total sum difference. It then finds the optimal replacement for each element using binary search on the sorted array nums1_sorted to find the closest elements to those in nums2, thus minimizing the absolute difference.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time complexity: O(n log n)
Space complexity: O(n) for sorting

Try this approach in the editor →

Approach 3: Sorting + Binary Search

According to the problem, we can first calculate the absolute difference sum of nums1 and nums2 without any replacements, denoted as s.

Next, we enumerate each element nums1[i] in nums1, replacing it with the element closest to nums2[i] that also exists in nums1. Therefore, before the enumeration, we can make a copy of nums1, resulting in the array nums, and sort nums. Then, we perform a binary search in nums for the element closest to nums2[i], denoted as nums[j], and calculate |nums1[i] - nums2[i]| - |nums[j] - nums2[i]|, updating the maximum value of the difference mx.

Finally, we subtract mx from s, which is the answer. Note the modulus operation.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums1.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time complexity: O(n^2)
Space complexity: O(1) (ignoring input size)

Optimized Approach using Binary Search

Time complexity: O(n log n)
Space complexity: O(n) for sorting

Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ReplacementO(n^2)O(1)Useful for understanding the replacement logic or when input size is very small
Sorted Array + Binary SearchO(n log n)O(n)General case and interview solution where fast nearest-value lookup is required

Video Solution

LeetCode 1818. Minimum Absolute Sum Difference | Medium | 🏆 Weekly Contest 235 | Algorithm Explained • Cherry Coding [IIT-G] • 9,243 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Minimum Absolute Sum Difference easy or hard?
Minimum Absolute Sum Difference is rated Medium on LeetCode. The brute force idea is straightforward, but identifying that the optimal replacement must be the closest value to nums2[i] requires algorithmic insight and knowledge of binary search on sorted data.
Minimum Absolute Sum Difference Python/Java solution
Python and Java implementations typically sort a copy of nums1 and use binary search (bisect in Python or Arrays.binarySearch in Java). For each index, they check the closest candidate values and compute the best reduction in absolute difference. The final answer is taken modulo 1e9+7 as required by the problem.
How to solve Minimum Absolute Sum Difference in O(n log n)?
Sort a copy of nums1 and compute the initial total absolute difference. For each index i, use binary search to find the closest value in the sorted array to nums2[i]. Calculate the potential improvement from replacing nums1[i] and track the maximum reduction. Subtract that reduction from the original sum.
What is the best approach for Minimum Absolute Sum Difference?
The optimal approach sorts a copy of nums1 and uses binary search to find the closest value to nums2[i] for each index. This lets you compute the maximum possible reduction in absolute difference from a single replacement. The algorithm runs in O(n log n) time due to sorting and binary searches.
Is Minimum Absolute Sum Difference asked at Google/Amazon/Meta?
Minimum Absolute Sum Difference is a typical medium-level array and binary search problem seen in interviews at companies like Amazon, Google, and other large tech firms. It tests understanding of greedy improvement, sorted structures, and efficient search techniques.
What data structure is used in Minimum Absolute Sum Difference?
The optimized solution relies on a sorted array structure that supports binary search. Some implementations also use ordered sets or balanced trees to find the closest value efficiently. The core idea is performing nearest-value queries in O(log n) time.
What is the time complexity of Minimum Absolute Sum Difference?
The optimized solution runs in O(n log n) time and O(n) space. Sorting nums1 takes O(n log n), and each of the n iterations performs a binary search in O(log n). A naive brute force replacement approach would take O(n^2) time.

Ready to solve this problem?

Practice Minimum Absolute Sum Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimize the Maximum Adjacent Element Difference

Next

Minimum Sum of Squared Difference