Sum of Absolute Differences in a Sorted Array-Algorithms&Visualizations

Federico Feresini

Follow

Dec 14, 2020 · 6 min read

Introduction
In this article, we will be going through the solution to a coding challenge that I’ve recently had the pleasure to solve taking one of the LeetCode contests. Other than the solution itself, I’ll be providing an easy visualization that hopefully will make everything really simple to grasp.

The problem
I’m not going to spend much time here, let me just copy-paste the description of this problem titled “Sum of Absolute Differences in a Sorted Array”

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

Constraints:
2 <= nums.length <= 10⁵
1 <= nums[i] <= nums[i + 1] <= 10^4

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

result[0] = |1–1|+|1–4|+|1–6|+|1–8|+|1–10| = 24
result[1] = |4–1|+|4–4|+|4–6|+|4–8|+|4–10| = 15
result[2] = |6–1|+|6–4|+|6–6|+|6–8|+|6–10| = 13
result[3] = |8–1|+|8–4|+|8–6|+|8–8|+|8–10| = 15
result[4] = |10–1|+|10–4|+|10–6|+|10–8|+|10–10| = 13

The problem should be clear, let’s jump into the study of the problem.

First Approach
The first approach crossing your mind might be picking one element at a time, and looping over all the others to compute the absolute differences. This is not a wrong approach in general, nevertheless, it doesn’t lend itself to a big amount of data. Looking at the constraints, we might run into arrays comprising 10⁵ elements, and an algorithm running in O(n²) will trigger the Time Limit Exceeded before getting the result.

Let’s jump into a real first approach, that seems better than just iterating every time over the whole array. What about saving some pieces of information while computing the solution? Let’s have a closer look at what we need:

Each line represents an entry of the final array result.

The first thing that grabbed my attention was the relationship between one line and the one above.

I realized that instead of iterating over all of the elements every time, I could have skipped some of the first ones because I had already computed them in the previous step. Check this out!

Interesting, isn’t it?

It means that if I kept an array storing the partial sum of absolute differences for each column of this sort of matrix, I could iterate only on a part of the given input array elements, instead of going through all of them each time.

This is an optimization of the first straightforward approach. Sounds great, right?

Well, it does, but unfortunately, the time complexity of the algorithm is still O(n²).

A failing algorithm always hurts, I know, however, we haven’t exploited important information about this problem. The array is sorted!

Second Approach
The elements are sorted. How can we leverage this information?
Obviously, picked an element, we know that all the previous ones are smaller, and the next ones are bigger (no duh!).

And what about the absolute difference between elements?
Let’s take a give arrays nums = [1, 4, 6, 9, 14]

Given the element [6], the distances to the other elements are drawn as yellow lines below the elements. Let’s pick the next element now, [9]

In the picture, I left the previous distances from element [6] to all the others in yellow, and then I just added up or subtracted the needed amount to get the distances from [9] to the other elements (purple lines).

Can you see the pattern here? We have kept all the previously computed distances from element [6], and then made some small changes to come up with the distances from element [9].

Here is the core of the algorithm that will allow us to solve this challenge. I want to make sure that the point I am trying to get across is extremely clear, and there’s no better way than some extra visualizations:

In the above picture, the upper section displays the distances from element [4] to all the others, while at the bottom from [6].
Let’s put one closer to the other, to have a better understanding.

As you can see from this latest visualization, the red and the green lines differ from each other to a fixed amount, which is always the distance from [4] to [6].
In other words, let’s focus on the distance from [1] to [4] and from [1] to [6]:

Simple right? The distance from [6] to [1] is nothing short of the distance from [1] to [4] plus the distance from [4] to [6].
Ok, let’s move along towards a second couple of distances:

This is pretty obvious! The distance from [6] to [4] is the same that we had computed during the previous step from [4] to [6].

Let’s go to the next ones:

Here it’s simple to see that the distance from [6] to [9], is the same distance between [4] to [9], but after removing the distance between [4] to [6].

Last but not least!

It must be clear now that the distance from [6] to [14] can be computed either as |6-14| or |4-14|-|4-6|.

A visualization to sum everything up:

In a nutshell, we can easily compute the sum of the differences from [6] to all the other elements, simply knowing in advance the sum of the differences from [4] because:
|6–1| = |4-1| + |4-6|
|6–4| = |4-6|
|6–9| = |4-9| -|4-6|
|6–14| = |4-14|- |4–6|

Should be quite easy to spot that:

I hope that at this point the idea is clear, let’s jump into the code now.

The Code

Conclusions
I hope that you liked this article hopefully learned something new. Have a good day!

“Example isn`t another way to teach, it is the only way to teach.” — Albert Einstein