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

Federico Feresini
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

The Startup

Get smarter at building your thing. Join The Startup’s +786K followers.

Sign up for Top 10 Stories

By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Federico Feresini

Written by

Software Engineer

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +786K followers.

Federico Feresini

Written by

Software Engineer

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +786K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store