Sum of Absolute Differences in a Sorted Array-Algorithms&Visualizations
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.
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
numssorted in non-decreasing order.
Build and return an integer array
resultwith the same length as
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
0 <= j < nums.lengthand
j != i(0-indexed).
2 <= nums.length <=10⁵
1 <= nums[i] <= nums[i + 1] <= 10^4
Input: nums = [1, 4, 6, 8, 10]
Output: result = [24,15,13,15,21]
result = |1–1|+|1–4|+|1–6|+|1–8|+|1–10| = 24
result = |4–1|+|4–4|+|4–6|+|4–8|+|4–10| = 15
result = |6–1|+|6–4|+|6–6|+|6–8|+|6–10| = 13
result = |8–1|+|8–4|+|8–6|+|8–8|+|8–10| = 15
result = |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.
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!
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 , the distances to the other elements are drawn as yellow lines below the elements. Let’s pick the next element now, 
In the picture, I left the previous distances from element  to all the others in yellow, and then I just added up or subtracted the needed amount to get the distances from  to the other elements (purple lines).
Can you see the pattern here? We have kept all the previously computed distances from element , and then made some small changes to come up with the distances from element .
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  to all the others, while at the bottom from .
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  to .
In other words, let’s focus on the distance from  to  and from  to :
Simple right? The distance from  to  is nothing short of the distance from  to  plus the distance from  to .
Ok, let’s move along towards a second couple of distances:
This is pretty obvious! The distance from  to  is the same that we had computed during the previous step from  to .
Let’s go to the next ones:
Here it’s simple to see that the distance from  to , is the same distance between  to , but after removing the distance between  to .
Last but not least!
It must be clear now that the distance from  to  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  to all the other elements, simply knowing in advance the sum of the differences from  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.
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