Formatted question description: https://leetcode.ca/all/1685.html

# 1685. Sum of Absolute Differences in a Sorted Array

Medium

## 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 = 2-2 + 2-3 + 2-5 = 0 + 1 + 3 = 4,
 result = 3-2 + 3-3 + 3-5 = 1 + 0 + 2 = 3,
 result = 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

## Solution

Let n be the length of nums. Create two arrays leftDifferences and rightDifferences that both have length n. Calculate leftDifferences as the sum of absolute differences between nums and all the other elements in nums. For i from 1 to n - 1, let difference = nums[i] - nums[i - 1] and calculate leftDifferences[i] = leftDifferences[i - 1] - difference - difference * (n - 1 - i). Calculate rightDifferences[n - 1] as the sum of absolute differences between nums[n - 1] and all the other elements in nums. For i from n - 2 to 0, let difference = nums[i + 1] - nums[i] and calculate rightDifferences[i] = rightDifferences[i + 1] - difference - difference * i. For the array result, there is result[i] = leftDifferences[i] + rightDifferences[i] for all 0 <= i < n. Finally, return result.

class Solution {
public int[] getSumAbsoluteDifferences(int[] nums) {
int length = nums.length;
int[] leftDifferences = new int[length];
for (int i = 1; i < length; i++)
leftDifferences += nums[i] - nums;
for (int i = 1; i < length; i++) {
int difference = nums[i] - nums[i - 1];
leftDifferences[i] = leftDifferences[i - 1] - difference - difference * (length - 1 - i);
}
int[] rightDifferences = new int[length];
for (int i = length - 2; i >= 0; i--)
rightDifferences[length - 1] += nums[length - 1] - nums[i];
for (int i = length - 2; i >= 0; i--) {
int difference = nums[i + 1] - nums[i];
rightDifferences[i] = rightDifferences[i + 1] - difference - difference * i;
}
int[] differences = new int[length];
for (int i = 0; i < length; i++)
differences[i] = leftDifferences[i] + rightDifferences[i];
return differences;
}
}