# Sum of Absolute Differences in a Sorted Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-absolute-differences-in-a-sorted-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** 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**).

**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 <= 105`
* `1 <= nums[i] <= nums[i + 1] <= 104`

# Approaches
## Brute Force
The most straightforward method is to directly implement the problem's definition. For each element `nums[i]`, we can iterate through the entire array `nums` again, calculate the absolute difference with every other element `nums[j]`, and sum these differences up. This gives us the value for `result[i]`.
**Time:** O(N^2), where N is the number of elements in `nums`. For each of the N elements, we perform another N operations inside the inner loop. · **Space:** O(N) to store the output array. If the output array is not considered extra space, the complexity is O(1).
**Pros:** Very simple to understand and implement directly from the problem statement.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
This approach uses a nested loop. The outer loop selects an element `nums[i]`, and the inner loop iterates over all elements `nums[j]` in the array. For each pair `(i, j)`, we compute `Math.abs(nums[i] - nums[j])` and add it to a temporary sum. Once the inner loop is finished, this sum is the value for `result[i]`. This process is repeated for every element in the `nums` array.

```java
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = 0; j < n; j++) {
                currentSum += Math.abs(nums[i] - nums[j]);
            }
            result[i] = currentSum;
        }
        return result;
    }
}
```
### Algorithm
- Initialize a `result` array of the same size as `nums`.
- Use a nested loop structure. The outer loop iterates through each element `nums[i]` from `i = 0` to `n-1`.
- The inner loop iterates through each element `nums[j]` from `j = 0` to `n-1`.
- Inside the inner loop, calculate the absolute difference `|nums[i] - nums[j]|`.
- Add this difference to a running sum variable, say `currentSum`, which is initialized to 0 for each `i`.
- After the inner loop completes, assign `currentSum` to `result[i]`.
- After the outer loop finishes, return the `result` array.

## Prefix Sums
A more efficient approach leverages the fact that the input array `nums` is sorted. This allows us to remove the absolute value from the calculation by splitting the sum into two parts: the sum of differences with elements to the left and the sum of differences with elements to the right. We can use a prefix sum array to quickly find the sum of elements in any subarray.
**Time:** O(N), as it involves a pass to build the prefix sum array and another pass to compute the results. · **Space:** O(N) to store the prefix sum array and the result array.
**Pros:** Significantly faster than the brute-force approach with a linear time complexity.; Efficient enough to pass the given constraints.
**Cons:** Requires additional space proportional to the input size for the prefix sum array.
### Explanation
Since `nums` is sorted, for any `nums[i]`, all elements `nums[j]` with `j < i` are less than or equal to `nums[i]`, and all elements `nums[j]` with `j > i` are greater than or equal to `nums[i]`. The formula for `result[i]` can be expanded as:
`result[i] = sum(nums[i] - nums[j]) for j < i` + `sum(nums[j] - nums[i]) for j > i`.
This simplifies to:
`result[i] = (i * nums[i] - sum_left) + (sum_right - (n-1-i) * nums[i])`.
To get `sum_left` (sum of elements before `i`) and `sum_right` (sum of elements after `i`) efficiently, we can precompute a prefix sum array. This allows us to find these sums in O(1) time for each `i`.

```java
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int[] result = new int[n];
        int totalSum = prefixSum[n];

        for (int i = 0; i < n; i++) {
            int leftSum = prefixSum[i];
            int rightSum = totalSum - prefixSum[i + 1];

            int leftCount = i;
            int rightCount = n - 1 - i;

            int leftTotal = leftCount * nums[i] - leftSum;
            int rightTotal = rightSum - rightCount * nums[i];

            result[i] = leftTotal + rightTotal;
        }
        return result;
    }
}
```
### Algorithm
- First, create a prefix sum array, let's call it `prefix`, of size `n+1`.
- Iterate through `nums` to populate `prefix`, where `prefix[i]` stores the sum of the first `i` elements of `nums`. So, `prefix[i+1] = prefix[i] + nums[i]`.
- The total sum of all elements, `totalSum`, will be `prefix[n]`.
- Create a `result` array of size `n`.
- Iterate from `i = 0` to `n-1`:
  - The sum of elements to the left of `i` is `leftSum = prefix[i]`.
  - The sum of elements to the right of `i` is `rightSum = totalSum - prefix[i+1]`.
  - The number of elements to the left is `leftCount = i`.
  - The number of elements to the right is `rightCount = n - 1 - i`.
  - Calculate `result[i] = (leftCount * nums[i] - leftSum) + (rightSum - rightCount * nums[i])`.
- Return the `result` array.

## Single Pass with Constant Extra Space
This approach is an optimization of the prefix sum method. Instead of pre-calculating and storing the entire prefix sum array, we can achieve the same result in a single pass with constant extra space. We do this by dynamically maintaining the sum of elements to the left (`leftSum`) and calculating the sum of elements to the right (`rightSum`) on the fly.
**Time:** O(N). We make one pass to get the total sum and another pass to compute the results, leading to an overall linear time complexity. · **Space:** O(1) extra space. We only use a few variables to keep track of sums. The O(N) space for the output array is generally not counted as extra space.
**Pros:** Optimal solution with linear time complexity.; Space-efficient, using only constant extra space (excluding the output array).
**Cons:** The logic can be slightly less intuitive to derive compared to the more direct brute-force or prefix sum array approaches.
### Explanation
The mathematical formula for `result[i]` remains the same: `result[i] = (i * nums[i] - leftSum) + (rightSum - (n - 1 - i) * nums[i])`. We start by calculating the `totalSum` of the array. Then, we iterate through the array, maintaining a `leftSum` variable. In each step `i`, `leftSum` holds the sum of elements `nums[0]` through `nums[i-1]`. The `rightSum` can then be found by subtracting `leftSum` and the current element `nums[i]` from `totalSum`. After calculating `result[i]`, we update `leftSum` by adding `nums[i]` to it, making it ready for the next iteration. This avoids the need for an O(N) prefix sum array.

```java
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int[] result = new int[n];
        int leftSum = 0;
        for (int i = 0; i < n; i++) {
            int rightSum = totalSum - leftSum - nums[i];

            int leftCount = i;
            int rightCount = n - 1 - i;

            int leftTotal = leftCount * nums[i] - leftSum;
            int rightTotal = rightSum - rightCount * nums[i];

            result[i] = leftTotal + rightTotal;
            
            leftSum += nums[i];
        }
        return result;
    }
}
```
### Algorithm
- First, iterate through the `nums` array once to calculate the `totalSum` of all its elements.
- Initialize a `result` array of size `n` and a `leftSum` variable to 0.
- Iterate through the `nums` array from `i = 0` to `n-1`:
  - Calculate the `rightSum` for the current element `nums[i]` using the formula: `rightSum = totalSum - leftSum - nums[i]`.
  - The number of elements to the left is `leftCount = i`.
  - The number of elements to the right is `rightCount = n - 1 - i`.
  - Calculate `result[i]` using the same formula as the prefix sum approach: `result[i] = (leftCount * nums[i] - leftSum) + (rightSum - rightCount * nums[i])`.
  - After calculating `result[i]`, update `leftSum` for the next iteration by adding the current element: `leftSum += nums[i]`.
- Return the `result` array.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] GetSumAbsoluteDifferences(int[] nums) {
        int s = 0, t = 0;
        foreach(int x in nums) {
            s += x;
        }
        int n = nums.Length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int v = nums[i] * i - t + s - t - nums[i] * (n - i);
            ans[i] = v;
            t += nums[i];
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int[] getSumAbsoluteDifferences(int[] nums) {
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var getSumAbsoluteDifferences =
  function (nums) {
    const s = nums.reduce((a, b) => a + b);
    let t = 0;
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; ++i) {
      const v = nums[i] * i - t + s - t - nums[i] * (n - i);
      ans[i] = v;
      t += nums[i];
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> getSumAbsoluteDifferences(vector<int> &nums) {
    int s = accumulate(nums.begin(), nums.end(), 0), t = 0;
    int n = nums.size();
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      int v = nums[i] * i - t + s - t - nums[i] * (n - i);
      ans[i] = v;
      t += nums[i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]: ans = [] s, t = sum(nums), 0 for i, x in enumerate(nums): v = x * i - t + s - t - x * (len(nums) - i) ans . append(v) t += x return ans

```