Sum of Absolute Differences in a Sorted Array

Sum of Absolute Differences in a Sorted Array

What is this problem about?

In this problem, you are given a sorted array of integers. For each element at index i, you need to calculate the sum of the absolute differences between that element and every other element in the array. For example, if the array is [1, 4, 6] and you are looking at the element '4', you need to compute |4-1| + |4-4| + |4-6| = 3 + 0 + 2 = 5. You must return an array of these sums.

Why is this asked in interviews?

Companies like Meta and Google ask this to see if a candidate can optimize a calculation from O(N²) to O(N). The sorted property of the array is a huge hint. It tests the candidate's ability to use mathematical properties of sums to avoid redundant calculations. It also tests the implementation of prefix sums, a core concept in array optimization.

Algorithmic pattern used

The pattern used is Prefix Sums (or Cumulative Sums). Since the array is sorted, for any element nums[i], all elements to its left are smaller (or equal) and all elements to its right are larger (or equal).

• The sum of differences for elements to the left is: (nums[i] * count_left) - sum_left.
• The sum of differences for elements to the right is: sum_right - (nums[i] * count_right). By pre-calculating the total sum of the array, we can derive sum_left and sum_right in constant time as we iterate through the array.

Example explanation

Array: [1, 4, 6]. Total Sum = 11.

• At index 1 (value 4):
  • Left: [1]. sum_left = 1, count_left = 1. Difference = (4 * 1) - 1 = 3.
  • Right: [6]. sum_right = 6, count_right = 1. Difference = 6 - (4 * 1) = 2.
  • Total = 3 + 2 = 5.
• At index 0 (value 1):
  • Left: []. sum_left = 0, count_left = 0. Difference = 0.
  • Right: [4, 6]. sum_right = 10, count_right = 2. Difference = 10 - (1 * 2) = 8.
  • Total = 8.

Common mistakes candidates make

1. Using Nested Loops: Writing an O(N²) solution that fails for large arrays.
2. Off-by-one errors: Incorrectly calculating the count of elements to the left or right of the current index.
3. Missing the Sorted property: Failing to realize that the sorted order allows us to remove the absolute value signs by splitting the sum into two parts (left and right).

Interview preparation tip

Always pay attention to whether an array is sorted. If it is, absolute differences can almost always be simplified. Practice calculating prefix sums on the fly using a single variable (current_running_sum) to keep your space complexity at O(1) beyond the output array.