python - Fastest way to find the smallest possible sum of the absolute differences of pairs within a single array? - Stack Overf

By grouping all the items within an array into pairs and getting their absolute differences, what is the minimum sum of their absolute differences?

Example:

[4, 1, 2, 3] should return 2 because |1 - 2| + |3 - 4| = 2
[1, 3, 3, 4, 5] should return 1 because |3 - 3| + |4 - 5| = 1

Getting the result for arrays with an even length is pretty easy, because it just requires sorting the array and getting the differences between numbers right next to each other.

However, arrays with an odd length are pretty hard because the addition of an extra number. Thus, my current solution for odd length arrays is to remove each number and check the sum using the even-length array approach.

Current solution:

def smallest_sum(arr):
    arr = sorted(arr)
    if len(arr) % 2 == 0:
        return even_arr_sum(arr)
    else:
        return odd_arr_sum(arr)
    
def even_arr_sum(arr):
    total = 0
    for i in range(0, len(arr), 2):
        total += arr[i+1] - arr[i]
    return total

def odd_arr_sum(arr):
    total = 0
    for i in range(len(arr)):
        s = even_arr_sum(arr[:i] + arr[i+1:])
        if total == 0 or s < total:
            total = s
    return total

assert smallest_sum([4, 1, 2, 3]) == 2
assert smallest_sum([1, 3, 3, 4, 5]) == 1

However, this is extremely slow and gives a time of n2. Is there a smarter way to handle arrays with an odd length?

By grouping all the items within an array into pairs and getting their absolute differences, what is the minimum sum of their absolute differences?

Example:

[4, 1, 2, 3] should return 2 because |1 - 2| + |3 - 4| = 2
[1, 3, 3, 4, 5] should return 1 because |3 - 3| + |4 - 5| = 1

Getting the result for arrays with an even length is pretty easy, because it just requires sorting the array and getting the differences between numbers right next to each other.

However, arrays with an odd length are pretty hard because the addition of an extra number. Thus, my current solution for odd length arrays is to remove each number and check the sum using the even-length array approach.

Current solution:

def smallest_sum(arr):
    arr = sorted(arr)
    if len(arr) % 2 == 0:
        return even_arr_sum(arr)
    else:
        return odd_arr_sum(arr)
    
def even_arr_sum(arr):
    total = 0
    for i in range(0, len(arr), 2):
        total += arr[i+1] - arr[i]
    return total

def odd_arr_sum(arr):
    total = 0
    for i in range(len(arr)):
        s = even_arr_sum(arr[:i] + arr[i+1:])
        if total == 0 or s < total:
            total = s
    return total

assert smallest_sum([4, 1, 2, 3]) == 2
assert smallest_sum([1, 3, 3, 4, 5]) == 1

However, this is extremely slow and gives a time of n2. Is there a smarter way to handle arrays with an odd length?

• python
• arrays
• algorithm
• time-complexity

Share Follow asked Jan 30 at 11:10 CrypticCryptic 6311 silver badge33 bronze badges 10

• 1 [1, 3, 3, 4, 5] should return 1 because |3 - 3| + |4 - 5| = 1 -- in your test, you're ignoring the first, smallest element. Why don't you do the same in your algorithm? Sort in O(n log n), then if length is odd pop off the first element. – LSerni Commented Jan 30 at 11:14
• @LSerni Perhaps because it doesn't work in all cases. – n. m. could be an AI Commented Jan 30 at 11:16
• @n.m.couldbeanAI Granted that, but my question stands - why was this result considered acceptable? The requirement is "... SHOULD return 1". What I mean is, the algorithm to be used to calculate the answer is unclear to me. – LSerni Commented Jan 30 at 11:18
• @LSerni This would not work for arrays like [1, 1, 5, 10, 11]. In this case, removing the first element, 1, will give a sum of 5, while removing the third element, 5, will give a sum of 1. – Cryptic Commented Jan 30 at 11:21
• @n.m.couldbeanAI The sums change? I'm sorry, I don't understand the question. – Cryptic Commented Jan 30 at 11:28

 |  Show 5 more comments

1 Answer 1

Sorted by: Reset to default 9

Imagine you have sorted seven numbers A to G and you leave out A, thus calculating (C-B)+(E-D)+(G-F). That's adding or subtracting them like this:

A B C D E F G
  - + - + - +  (leaving out A)

And this is how it looks in general, for leaving out each of the numbers:

A B C D E F G
  - + - + - +  (leaving out A)
-   + - + - +  (leaving out B)
- +   - + - +  ...
- + -   + - +
- + - +   - +
- + - + -   +
- + - + - +  

From one row to the next, there's little change. So first compute the total for leaving out A. Then for the total for leaving out B, simply subtract A and add B. And so on.