Sum of Absolute Differences in a Sorted Array

Sum of Absolute Differences in a Sorted Array - Problem

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

In other words, result[i] is equal to sum(|nums[i] - nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,5]

› Output: [4,3,5]

💡 Note: For nums[0]=2: |2-3| + |2-5| = 1 + 3 = 4. For nums[1]=3: |3-2| + |3-5| = 1 + 2 = 3. For nums[2]=5: |5-2| + |5-3| = 3 + 2 = 5.

Example 2 — Single Element

$ Input: nums = [1]

› Output: [0]

💡 Note: Only one element, so no other elements to compare with. Result is 0.

Example 3 — Larger Array

$ Input: nums = [1,4,6,8,10]

› Output: [24,15,13,15,24]

💡 Note: For nums[0]=1: |1-4|+|1-6|+|1-8|+|1-10| = 3+5+7+9 = 24. Similar calculations for other elements.

Constraints

2 ≤ nums.length ≤ 10⁵
nums is sorted in non-decreasing order
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array nums = [2,3,5]

Process

For each element, sum |nums[i] - nums[j]| for all j ≠ i

Output

Array of sums [4,3,5]

Key Takeaway

🎯 Key Insight: Use the sorted property with prefix sums to calculate differences in O(n) time instead of O(n²)

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is that since the array is sorted, we can use prefix sums to efficiently calculate the sum of absolute differences. For each element, all elements to the left are smaller and all elements to the right are larger. Best approach is prefix sum optimization with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n)	O(1)	Use prefix sums and the sorted property to calculate differences efficiently
Brute Force	O(n²)	O(1)	Calculate absolute difference between each element and all other elements

Prefix Sum Optimization — Algorithm Steps

Calculate prefix sum of the array
For each element, use prefix sum to get left and right contributions
Left contribution: i * nums[i] - leftSum
Right contribution: rightSum - (n-i-1) * nums[i]

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Calculate total sum and track left sum

Left Contribution

i * nums[i] - leftSum

Right Contribution

rightSum - (n-i-1) * nums[i]

Code -

solution.c — C

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

void solution(int* nums, int numsSize, int* result) {
    // Calculate total sum
    long long totalSum = 0;
    for (int i = 0; i < numsSize; i++) {
        totalSum += nums[i];
    }
    
    long long leftSum = 0;
    
    for (int i = 0; i < numsSize; i++) {
        // Right sum = totalSum - leftSum - nums[i]
        long long rightSum = totalSum - leftSum - nums[i];
        
        // Left contribution: i * nums[i] - leftSum
        // Right contribution: rightSum - (n - i - 1) * nums[i]
        long long leftContribution = (long long) i * nums[i] - leftSum;
        long long rightContribution = rightSum - (long long) (numsSize - i - 1) * nums[i];
        
        result[i] = leftContribution + rightContribution;
        
        // Update leftSum for next iteration
        leftSum += nums[i];
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result[1000];
    solution(nums, numsSize, result);
    
    printf("[");
    for (int i = 0; i < numsSize; i++) {
        printf("%d", result[i]);
        if (i < numsSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to calculate prefix sums and results

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables besides result array

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler