Sum of Absolute Differences in a Sorted Array

Medium
1140.

Sum of Absolute Differences in a Sorted Array

Sum of Absolute Differences in a Sorted Array is a medium coding problem on arrays, math and prefix sum, asked in Amazon and Google interviews.

nums is sorted in non-decreasing order.

Return an array result of the same length where result[i] is the sum of |nums[i] - nums[j]| over every index j of the array (the term for j = i is zero).

Example 1

Input
nums = [2,5,9]
Output
[10,7,11]
Explanation
`result[1] = |5-2| + |5-5| + |5-9| = 3 + 0 + 4 = 7`.

Example 2

Input
nums = [1,1,4]
Output
[3,3,6]

Example 3

Input
nums = [7,7]
Output
[0,0]

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= nums[i + 1] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var getSumAbsoluteDifferences = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of Absolute Differences in a Sorted Array — Solution

Sum of Absolute Differences in a Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Sum of Absolute Differences in a Sorted Array is a medium coding problem on arrays, math and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums is sorted in non-decreasing order.

Return an array result of the same length where result[i] is the sum of |nums[i] - nums[j]| over every index j of the array (the term for j = i is zero).

Example 1

Input: nums = [2,5,9]
Output: [10,7,11]
Explanation: `result[1] = |5-2| + |5-5| + |5-9| = 3 + 0 + 4 = 7`.

Example 2

Input: nums = [1,1,4]
Output: [3,3,6]

Example 3

Input: nums = [7,7]
Output: [0,0]

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= nums[i + 1] <= 10^4

Hints for Sum of Absolute Differences in a Sorted Array

  1. Hint 1

    Because the array is sorted, every element left of i is at most nums[i] and every element right of it is at least nums[i].

  2. Hint 2

    So the left part contributes nums[i] * i - (sum of the left elements) and the right part (sum of the right elements) - nums[i] * (count on the right).

  3. Hint 3

    Keep a running prefix sum and the total; each result[i] is then O(1).

How to solve Sum of Absolute Differences in a Sorted Array

Sorting removes the absolute values: to the left of i every difference is nums[i] - nums[j], to the right it is nums[j] - nums[i], and both sides collapse into prefix-sum formulas.

Approach

  1. Compute total, the sum of all elements, and sweep i with left, the sum of nums[0..i-1].
  2. right = total - left - nums[i] is the sum of nums[i+1..n-1].
  3. result[i] = nums[i] * i - left + right - nums[i] * (n - 1 - i).
  4. Add nums[i] to left and continue.

Why it works

For j < i, nums[j] <= nums[i], so |nums[i] - nums[j]| = nums[i] - nums[j]; summing over the i such indices gives nums[i] * i - left. The right side is symmetric. Together they are exactly the requested sum.

Complexity

  • Time — O(n)
  • Space — O(1) besides the output

Pitfalls

  • The double loop is O(n^2) — too slow for 10^5 elements.
  • Mind the counts: i elements on the left, n - 1 - i on the right.
  • Each result is at most about 10^9 here, which fits in 32 bits; use 64-bit intermediates if the bounds grow.

Reference solution

Python

from typing import List

def getSumAbsoluteDifferences(nums: List[int]) -> List[int]:
    n = len(nums)
    total = sum(nums)
    left = 0
    result = []
    for i, x in enumerate(nums):
        right = total - left - x
        result.append(x * i - left + right - x * (n - 1 - i))
        left += x
    return result

Java

public static int[] getSumAbsoluteDifferences(int[] nums) {
    int n = nums.length;
    long total = 0, left = 0;
    for (int v : nums) total += v;
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        long x = nums[i];
        long right = total - left - x;
        result[i] = (int) (x * i - left + right - x * (n - 1 - i));
        left += x;
    }
    return result;
}

C++

vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
    int n = nums.size();
    long long total = 0, left = 0;
    for (int v : nums) total += v;
    vector<int> result(n);
    for (int i = 0; i < n; i++) {
        long long x = nums[i];
        long long right = total - left - x;
        result[i] = (int)(x * i - left + right - x * (n - 1 - i));
        left += x;
    }
    return result;
}

JavaScript

var getSumAbsoluteDifferences = function(nums) {
    var n = nums.length, total = 0, left = 0;
    for (var i = 0; i < n; i++) total += nums[i];
    var result = new Array(n);
    for (var j = 0; j < n; j++) {
        var x = nums[j];
        var right = total - left - x;
        result[j] = x * j - left + right - x * (n - 1 - j);
        left += x;
    }
    return result;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum