Problem Description

You are given an integer array nums that is sorted in non-decreasing order.

Your task is to build and return a new integer array result with the same length as nums. Each element result[i] should be equal to the sum of absolute differences between nums[i] and all other elements in the array.

More specifically, for each index i, you need to calculate:

• result[i] = |nums[i] - nums[0]| + |nums[i] - nums[1]| + ... + |nums[i] - nums[n-1]| (excluding |nums[i] - nums[i]|)

Since the array is sorted, we can optimize the calculation. For any element nums[i]:

• All elements to the left (nums[0] to nums[i-1]) are smaller than or equal to nums[i]
• All elements to the right (nums[i+1] to nums[n-1]) are greater than or equal to nums[i]

This means:

• For elements on the left: |nums[i] - nums[j]| = nums[i] - nums[j]
• For elements on the right: |nums[i] - nums[j]| = nums[j] - nums[i]

The solution uses prefix sums to efficiently calculate these differences. It maintains:

• s: the total sum of all elements
• t: the running sum of elements processed so far
• For each nums[i], the formula nums[i] * i - t + s - t - nums[i] * (len(nums) - i) calculates the sum of absolute differences

This formula works because:

• nums[i] * i - t gives the sum of differences with elements on the left
• s - t - nums[i] * (len(nums) - i) gives the sum of differences with elements on the right (including the current element, which gets subtracted out)

Intuition

The key insight comes from recognizing that the array is sorted in non-decreasing order. This property allows us to avoid calculating absolute values conditionally.

For any element nums[i] in a sorted array:

• All elements before it (indices 0 to i-1) are smaller or equal, so |nums[i] - nums[j]| = nums[i] - nums[j]
• All elements after it (indices i+1 to n-1) are greater or equal, so |nums[i] - nums[j]| = nums[j] - nums[i]

Let's think about how to calculate the sum of absolute differences for nums[i]:

Left side contribution:

• We need (nums[i] - nums[0]) + (nums[i] - nums[1]) + ... + (nums[i] - nums[i-1])
• This simplifies to nums[i] * i - (nums[0] + nums[1] + ... + nums[i-1])
• Which is nums[i] * i - t, where t is the sum of all elements before index i

Right side contribution:

• We need (nums[i+1] - nums[i]) + (nums[i+2] - nums[i]) + ... + (nums[n-1] - nums[i])
• This simplifies to (nums[i+1] + nums[i+2] + ... + nums[n-1]) - nums[i] * (n - i - 1)
• The sum of elements after i is s - t - nums[i], where s is the total sum
• So the contribution becomes (s - t - nums[i]) - nums[i] * (n - i - 1)
• Which simplifies to s - t - nums[i] * (n - i)

Combining both contributions: result[i] = nums[i] * i - t + s - t - nums[i] * (n - i)

By maintaining a running sum t as we iterate through the array, we can calculate each result[i] in constant time, giving us an overall linear time complexity.

Learn more about Math and Prefix Sum patterns.

Solution Approach

We use a summation and enumeration approach to solve this problem efficiently in O(n) time.

Algorithm Steps:

1. Initialize variables:

   • Calculate s = sum(nums) - the total sum of all elements in the array
   • Initialize t = 0 - this will track the cumulative sum of elements we've processed
   • Create an empty list ans to store our results

2. Iterate through each element: For each element nums[i] at index i:

   • Apply the formula:

     v = nums[i] * i - t + s - t - nums[i] * (len(nums) - i)

     This formula combines:

     • nums[i] * i - t: Sum of differences with elements on the left
     • s - t - nums[i] * (len(nums) - i): Sum of differences with elements on the right

   • Store the result: Append v to our answer list

   • Update the running sum: Add the current element to t with t += nums[i]

3. Return the result: After processing all elements, return the ans list

Implementation Details:

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

The solution cleverly avoids nested loops by:

• Pre-computing the total sum s once at the beginning
• Maintaining a running sum t to know the sum of elements before the current position
• Using arithmetic to calculate the sum of elements after the current position as s - t - nums[i]

Time Complexity: O(n) - We iterate through the array once after calculating the initial sum Space Complexity: O(1) - We only use a constant amount of extra space (excluding the output array)

Example Walkthrough

Let's walk through the solution with a small example: nums = [2, 3, 5]

Step 1: Initialize variables

• Calculate total sum: s = 2 + 3 + 5 = 10
• Initialize running sum: t = 0
• Create empty result list: ans = []

Step 2: Process each element

For i = 0, nums[0] = 2:

• Apply formula: v = 2 * 0 - 0 + 10 - 0 - 2 * (3 - 0)
  • Left contribution: 2 * 0 - 0 = 0 (no elements to the left)
  • Right contribution: 10 - 0 - 2 * 3 = 10 - 6 = 4
  • Total: v = 0 + 4 = 4
• Verify: |2-3| + |2-5| = 1 + 3 = 4 ✓
• Update: ans = [4], t = 0 + 2 = 2

For i = 1, nums[1] = 3:

• Apply formula: v = 3 * 1 - 2 + 10 - 2 - 3 * (3 - 1)
  • Left contribution: 3 * 1 - 2 = 1 (difference with 2)
  • Right contribution: 10 - 2 - 3 * 2 = 8 - 6 = 2 (difference with 5)
  • Total: v = 1 + 2 = 3
• Verify: |3-2| + |3-5| = 1 + 2 = 3 ✓
• Update: ans = [4, 3], t = 2 + 3 = 5

For i = 2, nums[2] = 5:

• Apply formula: v = 5 * 2 - 5 + 10 - 5 - 5 * (3 - 2)
  • Left contribution: 5 * 2 - 5 = 5 (differences with 2 and 3)
  • Right contribution: 10 - 5 - 5 * 1 = 0 (no elements to the right)
  • Total: v = 5 + 0 = 5
• Verify: |5-2| + |5-3| = 3 + 2 = 5 ✓
• Update: ans = [4, 3, 5], t = 5 + 5 = 10

Step 3: Return result

• Final answer: [4, 3, 5]

The formula efficiently calculates the sum by leveraging the sorted property, avoiding the need to compute absolute values individually.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array once with a single for loop, performing constant-time operations (arithmetic operations and list append) at each iteration. The initial sum(nums) operation also takes O(n) time, resulting in an overall time complexity of O(n) + O(n) = O(n).

The space complexity is O(1) if we exclude the output array ans. The algorithm only uses a constant amount of extra space for variables s, t, i, x, and v, regardless of the input size. If we include the output array ans which stores n elements, the space complexity would be O(n), but typically when analyzing space complexity, the space required for the output is not counted.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Large Arrays

When dealing with large arrays or large integer values, the intermediate calculations (especially total_sum and the formula components) might exceed the integer limit in some programming languages.

Example scenario:

• Array with 10^5 elements, each with value close to 10^9
• The total sum could reach 10^14, causing overflow in languages with 32-bit integers

Solution:

• In Python, this isn't an issue due to arbitrary precision integers
• In other languages (Java, C++), use long/long long data types
• Consider modular arithmetic if the problem requires it

2. Off-by-One Error in Formula

A common mistake is incorrectly calculating the number of elements on the right side, using (len(nums) - i) instead of (len(nums) - i - 1).

Incorrect formula:

# Wrong: includes the current element in right side count
sum_diff = current_value * index - cumulative_sum + 
           (total_sum - cumulative_sum) - current_value * (len(nums) - index)

Correct approach:

# Right: properly accounts for elements only after current position
sum_diff = current_value * index - cumulative_sum + 
           (total_sum - cumulative_sum - current_value) - current_value * (len(nums) - index - 1)

3. Forgetting to Update Cumulative Sum

Failing to update cumulative_sum after processing each element will cause incorrect calculations for subsequent elements.

Wrong implementation:

for index, current_value in enumerate(nums):
    sum_diff = current_value * index - cumulative_sum + 
               total_sum - cumulative_sum - current_value * (len(nums) - index)
    result.append(sum_diff)
    # Missing: cumulative_sum += current_value

Fix: Always update cumulative_sum += current_value at the end of each iteration.

4. Misunderstanding the Sorted Property

Attempting to use this formula on an unsorted array will produce incorrect results. The formula relies on the fact that all elements to the left are ≤ current element and all elements to the right are ≥ current element.

Solution:

• Verify the array is sorted before applying this algorithm
• If unsorted, either sort it first or use a different approach (brute force O(n²))

5. Edge Cases with Empty or Single-Element Arrays

Not handling edge cases properly can cause runtime errors or incorrect outputs.

Proper handling:

def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
    if not nums:  # Empty array
        return []
    if len(nums) == 1:  # Single element
        return [0]
  
    # Continue with main algorithm...