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

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4

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

Solution

Method 1 - Wrong Solution with Sum

One solution can be we sum up all the numbers, and

1

ans[i] = sum - nums[i];

Let’s see some examples to see why it is not valid:

1
2
3
4
5

nums = [2,3,5]
sum = 10
for 2: |10 - 2 * 3| = |2 - 2 + 3 - 2 + 5 - 2| = |8 - 4| = 4
for 3: |10 - 3 * 3| = |2 - 3 + 3 - 3 + 5 - 3| = |7 - 6| = 1
for 5: |10 - 5 * 3| = |2 - 5 + 3 - 5 + 5 - 5| = |5 - 10| = 5

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int[] getSumAbsoluteDifferences(int[] nums) {
	int n = nums.length;
	int[] ans = new int[n];

	
	long sum = Arrays.stream(nums).reduce(0, Integer::sum);
	
	for (int i = 0; i < n; i++) {
		ans[i] = Math.abs((int) (sum - n * nums[i]));

	}
	return ans;
}

Complexity

  • Time: O(n)
  • Space: O(1)

Method 2 - Using Prefix and Suffix Sum

Intuition

We use prefix and suffix sums to efficiently compute the sum of absolute differences for each index. By precomputing cumulative sums from both ends, we can calculate the left and right contributions for each element in constant time.

Approach

  1. Compute prefix sums and suffix sums for the array.
  2. For each index i, calculate:
    • Left: sum of differences with all elements before i.
    • Right: sum of differences with all elements after i.
  3. Combine left and right to get the result for each index.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n), suffix(n);
        prefix[0] = nums[0];
        suffix[n-1] = nums[n-1];
        for (int i = 1; i < n; ++i) {
            prefix[i] = prefix[i-1] + nums[i];
            suffix[n-i-1] = suffix[n-i] + nums[n-i-1];
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int left = nums[i] * i - prefix[i];
            int right = suffix[i] - nums[i] * (n - i - 1);
            ans[i] = left + right;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func getSumAbsoluteDifferences(nums []int) []int {
    n := len(nums)
    prefix := make([]int, n)
    suffix := make([]int, n)
    prefix[0] = nums[0]
    suffix[n-1] = nums[n-1]
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + nums[i]
        suffix[n-i-1] = suffix[n-i] + nums[n-i-1]
    }
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        left := nums[i]*i - prefix[i]
        right := suffix[i] - nums[i]*(n-i-1)
        ans[i] = left + right
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n];
        int[] suffixSum = new int[n];
        prefixSum[0] = nums[0];
        suffixSum[n - 1] = nums[n - 1];
        for (int i = 1; i < n; ++i) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
            suffixSum[n - i - 1] = suffixSum[n - i] + nums[n - i - 1];
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int left = nums[i] * i - prefixSum[i];
            int right = suffixSum[i] - nums[i] * (n - i - 1);
            ans[i] = left + right;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun getSumAbsoluteDifferences(nums: IntArray): IntArray {
        val n = nums.size
        val prefix = IntArray(n)
        val suffix = IntArray(n)
        prefix[0] = nums[0]
        suffix[n-1] = nums[n-1]
        for (i in 1 until n) {
            prefix[i] = prefix[i-1] + nums[i]
            suffix[n-i-1] = suffix[n-i] + nums[n-i-1]
        }
        val ans = IntArray(n)
        for (i in 0 until n) {
            val left = nums[i] * i - prefix[i]
            val right = suffix[i] - nums[i] * (n - i - 1)
            ans[i] = left + right
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def getSumAbsoluteDifferences(self, nums):
        n = len(nums)
        prefix = [0] * n
        suffix = [0] * n
        prefix[0] = nums[0]
        suffix[n-1] = nums[n-1]
        for i in range(1, n):
            prefix[i] = prefix[i-1] + nums[i]
            suffix[n-i-1] = suffix[n-i] + nums[n-i-1]
        ans = [0] * n
        for i in range(n):
            left = nums[i] * i - prefix[i]
            right = suffix[i] - nums[i] * (n - i - 1)
            ans[i] = left + right
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct Solution;

impl Solution {
    pub fn get_sum_absolute_differences(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut prefix = vec![0; n];
        let mut suffix = vec![0; n];
        prefix[0] = nums[0];
        suffix[n-1] = nums[n-1];
        for i in 1..n {
            prefix[i] = prefix[i-1] + nums[i];
            suffix[n-i-1] = suffix[n-i] + nums[n-i-1];
        }
        let mut ans = vec![0; n];
        for i in 0..n {
            let left = nums[i] * i as i32 - prefix[i];
            let right = suffix[i] - nums[i] * (n as i32 - i as i32 - 1);
            ans[i] = left + right;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    getSumAbsoluteDifferences(nums: number[]): number[] {
        const n = nums.length;
        const prefix = Array(n).fill(0);
        const suffix = Array(n).fill(0);
        prefix[0] = nums[0];
        suffix[n-1] = nums[n-1];
        for (let i = 1; i < n; ++i) {
            prefix[i] = prefix[i-1] + nums[i];
            suffix[n-i-1] = suffix[n-i] + nums[n-i-1];
        }
        const ans = Array(n).fill(0);
        for (let i = 0; i < n; ++i) {
            const left = nums[i] * i - prefix[i];
            const right = suffix[i] - nums[i] * (n - i - 1);
            ans[i] = left + right;
        }
        return ans;
    }
}