Sum of Absolute Differences in a Sorted Array

LeetCode 1787 | Difficulty: Medium

Medium

Problem Description

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).

Example 1:

Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.

Example 2:

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

Constraints:

- `2 <= nums.length <= 10^5`

- `1 <= nums[i] <= nums[i + 1] <= 10^4`

Topics: Array, Math, Prefix Sum

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 313 ms)

Metric	Value
Runtime	313 ms
Memory	49.6 MB
Date	2022-02-03

Solution

public class Solution {
    public int[] GetSumAbsoluteDifferences(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        
        for(int i=0;i<n;i++)
        {
            result[0] += nums[i]-nums[0];
        }
        
        for(int i=1;i<n;i++)
        {
            var numsBefore = i;
            var numsAfter = n-i;
            
            result[i] += result[i-1] + numsBefore*(nums[i]-nums[i-1]) - numsAfter*(nums[i]-nums[i-1]);
        }
        
        return result;
    }    
}

---

Complexity Analysis

Approach	Time	Space
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Absolute difference is the same as max(a, b) - min(a, b). How can you use this fact with the fact that the array is sorted?

Hint 2: For nums[i], the answer is (nums[i] - nums[0]) + (nums[i] - nums[1]) + ... + (nums[i] - nums[i-1]) + (nums[i+1] - nums[i]) + (nums[i+2] - nums[i]) + ... + (nums[n-1] - nums[i]).

Hint 3: It can be simplified to (nums[i] i - (nums[0] + nums[1] + ... + nums[i-1])) + ((nums[i+1] + nums[i+2] + ... + nums[n-1]) - nums[i] (n-i-1)). One can build prefix and suffix sums to compute this quickly.