Sum of Minimum Absolute Differences in an Array

Sorting the input array once converts a naive O(n²) pair-comparison into an O(n log n) scan, because in a sorted array each element’s nearest neighbour is always the element immediately to its left or right.

What “Minimum Absolute Difference” Means Per Element

The problem asks for the sum of n values, one per element. For each element at index i, compute the smallest |arr[i] - arr[j]| over every other index j where j != i. Sum all n of those minimum values.

The GeeksforGeeks article on this problem formalises it as:

• For each index i: MinAbsDiff(i) = min over all j != i of |arr[i] - arr[j]|
• Result = MinAbsDiff(0) + MinAbsDiff(1) + … + MinAbsDiff(n-1)

Note the distinction from a superficially similar problem: “find a single value x that minimises the sum of |arr[i] - x| for all i.” That related problem has the median as its optimal answer and produces a different result for the same input. The problem here asks for n individual minimums, summed together. Confusing the two leads to wrong answers on placement tests.

This problem shows up in the arrays section of coding rounds at IT service companies and mid-tier product companies. The expected interview progression: describe the brute-force O(n²) approach first, then optimise with sorting, and state both time and space complexity.

Naive Approach: O(n²) Double Loop

The direct reading of the problem leads to a nested loop. For each element at index i, scan every other element at index j and track the minimum |arr[i] - arr[j]|. After the inner loop finishes, add that minimum to a running total.

def min_abs_diff_sum_naive(arr):
    n = len(arr)
    total = 0
    for i in range(n):
        min_diff = float('inf')
        for j in range(n):
            if j != i:
                min_diff = min(min_diff, abs(arr[i] - arr[j]))
        total += min_diff
    return total

The outer loop runs n times and the inner loop runs n times, giving n × (n - 1) comparisons in total. For a thousand-element array, that amounts to close to a million comparisons. Time complexity is O(n²). The space complexity is O(1) auxiliary (only a handful of scalar variables).

This approach is correct but slow. Placement coding judges typically time out O(n²) solutions on inputs beyond a few thousand elements.

Optimal Approach: Sort, Then Scan Adjacent Pairs

The key insight: after sorting the array in ascending order, the nearest neighbour to any element is always one of its two immediate neighbours in the sorted result. An element cannot be closer to a non-adjacent element than to an adjacent one, because sorted order guarantees that elements further away in position are further away in value. One left-to-right pass after sorting is sufficient to collect all n per-element minimums.

Algorithm Steps

1. Sort the array in ascending order.
2. For index 0 (first element): only the right neighbour exists. MinAbsDiff = arr[1] - arr[0].
3. For index n-1 (last element): only the left neighbour exists. MinAbsDiff = arr[n-1] - arr[n-2].
4. For every interior index i (where 0 < i and i < n-1): MinAbsDiff = min(arr[i] - arr[i-1], arr[i+1] - arr[i]).
5. Sum all n MinAbsDiff values.

Time complexity: O(n log n) for sorting plus O(n) for the scan. The sort dominates, so the overall complexity is O(n log n).

Space complexity: O(1) auxiliary when the sort is in-place (as it is with C’s qsort, C++‘s std::sort, and Python’s list.sort).

This is similar in structure to the equilibrium index problem, where a single pass through the array (after precomputing a prefix sum) replaces repeated from-scratch computation. Both problems share the pattern: preprocess once, then scan linearly.

Step-by-Step Worked Example

Input: [4, 1, 3, 7] (n = 4)

After Sorting

Sorted order: [1, 3, 4, 7]

Per-Element Minimum Absolute Differences

• Index 0, value 1: only right neighbour exists. Gap = 3 - 1 = 2. MinAbsDiff = 2.
• Index 1, value 3: left gap = 3 - 1 = 2, right gap = 4 - 3 = 1. MinAbsDiff = min(2, 1) = 1.
• Index 2, value 4: left gap = 4 - 3 = 1, right gap = 7 - 4 = 3. MinAbsDiff = min(1, 3) = 1.
• Index 3, value 7: only left neighbour exists. Gap = 7 - 4 = 3. MinAbsDiff = 3.

Sum = 2 + 1 + 1 + 3 = 7

Brute-Force Verification

• Value 1: min(|1-3|, |1-4|, |1-7|) = min(2, 3, 6) = 2 ✓
• Value 3: min(|3-1|, |3-4|, |3-7|) = min(2, 1, 4) = 1 ✓
• Value 4: min(|4-1|, |4-3|, |4-7|) = min(3, 1, 3) = 1 ✓
• Value 7: min(|7-1|, |7-3|, |7-4|) = min(6, 4, 3) = 3 ✓

Both methods agree: the result is 7. The brute-force counted 12 comparisons (each of 4 elements against 3 others); the sorted scan needed only 4 adjacent comparisons after sorting.

Implementation in Python, C++, and C

All three implementations handle the two boundary elements (index 0 and index n-1) as separate cases since each has only one neighbour in the sorted array.

Python

def min_abs_diff_sum(arr):
    n = len(arr)
    if n <= 1:
        return 0
    arr.sort()
    total = 0
    for i in range(n):
        if i == 0:
            total += arr[1] - arr[0]
        elif i == n - 1:
            total += arr[n - 1] - arr[n - 2]
        else:
            total += min(arr[i] - arr[i - 1], arr[i + 1] - arr[i])
    return total

print(min_abs_diff_sum([4, 1, 3, 7]))   # 7
print(min_abs_diff_sum([1, 3, 3, 6]))   # 5
print(min_abs_diff_sum([5]))            # 0

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minAbsDiffSum(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return 0;
    sort(arr.begin(), arr.end());
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0)
            total += arr[1] - arr[0];
        else if (i == n - 1)
            total += arr[n - 1] - arr[n - 2];
        else
            total += min(arr[i] - arr[i - 1], arr[i + 1] - arr[i]);
    }
    return total;
}

int main() {
    vector<int> arr = {4, 1, 3, 7};
    cout << minAbsDiffSum(arr) << endl;  // 7
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int minAbsDiffSum(int arr[], int n) {
    if (n <= 1) return 0;
    qsort(arr, n, sizeof(int), compare);
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0)
            total += arr[1] - arr[0];
        else if (i == n - 1)
            total += arr[n - 1] - arr[n - 2];
        else {
            int left  = arr[i] - arr[i - 1];
            int right = arr[i + 1] - arr[i];
            total += (left < right) ? left : right;
        }
    }
    return total;
}

int main() {
    int arr[] = {4, 1, 3, 7};
    printf("%d\n", minAbsDiffSum(arr, 4));  // 7
    return 0;
}

After sorting, arr[i] - arr[i-1] is always non-negative for distinct elements, so abs() is unnecessary in the gap calculations. For arrays with duplicates, adjacent identical elements produce a gap of zero, which is correct. See the symmetric pairs in an array article for another array problem where sorting similarly reduces the naive O(n²) approach to a more efficient linear scan.

Edge Cases and Duplicates

Three situations require deliberate handling:

Single Element

An array with one element has no other elements to compare against, so every MinAbsDiff is undefined. The standard convention is to return 0. Both the Python and C implementations guard against this with an early return when n <= 1.

Two Elements

Both elements have only each other as neighbours. MinAbsDiff for both is |arr[0] - arr[1]|. The sum is therefore 2 * |arr[0] - arr[1]|.

Example: [10, 4] sorted to [4, 10].

• Element 4: gap to 10 = 6. MinAbsDiff = 6.
• Element 10: gap to 4 = 6. MinAbsDiff = 6.
• Sum = 12.

Arrays with Duplicates

Duplicate elements land adjacent in the sorted array, giving a zero gap. Each duplicate element that has an identical neighbour contributes 0 to the sum.

Example: [1, 3, 3, 6].

• Sorted: [1, 3, 3, 6]
• MinAbsDiff values: 2, 0, 0, 3
• Sum = 5

No algorithm change is needed. The gap between two adjacent identical elements evaluates to zero naturally.

The sort-and-scan insight works because sorted order makes the nearest neighbour always adjacent, replacing O(n²) comparisons with a single scan per element. That same pattern of exploiting a structural invariant to avoid redundant work shows up in production LLM pipelines that batch embedding lookups instead of computing vector distances one pair at a time. TinkerLLM is where engineering students build those kinds of systems hands-on, starting at ₹299.