Problem Statement

Given an integer array nums sorted in increasing order, return an array result of the same length, where result[i] should be the sum of the absolute differences between nums[i] and every other element in nums.

Examples

Example 1

• Input: [1, 3, 6]
• Output: [7, 5, 8]
• Explanation:
  • For result[0]: |1-3| + |1-6| = 2 + 5 = 7
  • For result[1]: |3-1| + |3-6| = 2 + 3 = 5
  • For result[2]: |6-1| + |6-3| = 5 + 3 = 8

Example 2

• Input: [2, 4, 7]
• Output: [7, 5, 8]
• Explanation:
  • For result[0]: |2-4| + |2-7| = 2 + 5 = 7
  • For result[1]: |4-2| + |4-7| = 2 + 3 = 5
  • For result[2]: |7-2| + |7-4| = 5 + 3 = 8

Example 3

• Input: [1, 2, 4, 5]
• Output: [8, 6, 6, 6]
• Explanation:
  • For result[0]: |1-2| + |1-4| + |1-5| = 1 + 3 + 4 = 8
  • For result[1]: |2-1| + |2-4| + |2-5| = 1 + 2 + 3 = 6
  • For result[2]: |4-1| + |4-2| + |4-5| = 3 + 2 + 1 = 6
  • For result[3]: |5-1| + |5-2| + |5-4| = 4 + 3 + 1 = 8

Constraints:

• 2 <= nums.length <= 10⁵
• 1 <= nums[i] <= nums[i + 1] <= 10⁴

Solution

To solve this problem, we need to calculate the sum of absolute differences for each element in the array. We can simplify this by using prefix sums to avoid repeatedly calculating the same differences. By leveraging prefix sums, we can compute the total difference more efficiently.

For each element, we will split the array into two parts: the left part and the right part. The left part includes all elements before the current one, and the right part includes all elements after the current one. Using the prefix sums, we can quickly get the sum of elements on the left and right, then use these sums to calculate the absolute differences. This method avoids the need for nested loops and reduces the time complexity.

Step-by-step Algorithm

1. Initialize Arrays:

   • Create an array result of the same length as nums initialized to zero.
   • Create an array prefixSum of length n + 1 (where n is the length of nums) initialized to zero.

2. Calculate Prefix Sums:

   • Iterate through the nums array.
   • For each index i, compute prefixSum[i + 1] = prefixSum[i] + nums[i].
   • This gives us the sum of all elements from the start up to index i.

3. Compute Result Array:

   • Iterate through the nums array.
   • For each index i:
     • Calculate the sum of the left part using prefixSum[i].
     • Calculate the sum of the right part using prefixSum[n] - prefixSum[i + 1].
     • Compute result[i] using the formula:
       • result[i] = (i * nums[i] - leftSum) + (rightSum - (n - i - 1) * nums[i])
     • The left part is i * nums[i] - leftSum.
     • The right part is rightSum - (n - i - 1) * nums[i].

4. Return Result:

   • Return the result array.

Algorithm Walkthrough

Let's consider the input: nums = {1, 2, 4, 5}

1. Initialize Arrays:

   • nums = [1, 2, 4, 5]
   • result = [0, 0, 0, 0]
   • prefixSum = [0, 0, 0, 0, 0]

2. Calculate Prefix Sums:

   • For i = 0, prefixSum[1] = prefixSum[0] + nums[0] = 0 + 1 = 1
     • prefixSum = [0, 1, 0, 0, 0]
   • For i = 1, prefixSum[2] = prefixSum[1] + nums[1] = 1 + 2 = 3
     • prefixSum = [0, 1, 3, 0, 0]
   • For i = 2, prefixSum[3] = prefixSum[2] + nums[2] = 3 + 4 = 7
     • prefixSum = [0, 1, 3, 7, 0]
   • For i = 3, prefixSum[4] = prefixSum[3] + nums[3] = 7 + 5 = 12
     • prefixSum = [0, 1, 3, 7, 12]

3. Compute Result Array:

   • For i = 0:
     • leftSum = prefixSum[0] = 0
     • rightSum = prefixSum[4] - prefixSum[1] = 12 - 1 = 11
     • result[0] = (0 * 1 - 0) + (11 - 3 * 1) = 0 + 8 = 8
       • result = [8, 0, 0, 0]
   • For i = 1:
     • leftSum = prefixSum[1] = 1
     • rightSum = prefixSum[4] - prefixSum[2] = 12 - 3 = 9
     • result[1] = (1 * 2 - 1) + (9 - 2 * 2) = 1 + 5 = 6
       • result = [8, 6, 0, 0]
   • For i = 2:
     • leftSum = prefixSum[2] = 3
     • rightSum = prefixSum[4] - prefixSum[3] = 12 - 7 = 5
     • result[2] = (2 * 4 - 3) + (5 - 1 * 4) = 5 + 1 = 6
       • result = [8, 6, 6, 0]
   • For i = 3:
     • leftSum = prefixSum[3] = 7
     • rightSum = prefixSum[4] - prefixSum[4] = 12 - 12 = 0
     • result[3] = (3 * 5 - 7) + (0 - 0 * 5) = 8 + 0 = 8
       • result = [8, 6, 6, 8]

4. Return Result:

   • The final result array is [8, 6, 6, 8].

Code