Abstract / Summary

Given a sorted list of integers, compute the sum of absolute differences between each pair of elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 68% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Math
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes, for each element in a sorted integer array, the sum of absolute differences between that element and every other element in the array. The method returns a generator that yields the result for each position in order, allowing the caller to consume the values lazily. The algorithm proceeds in a single forward pass while maintaining cumulative information about the left-hand side and right-hand side of the current index.

Key Steps

The function begins by establishing the size of the input and the total sum of all elements, which represents the initial right-hand contribution.

size  = len(nums)
right = sum(nums)
left  = 0
prev  = 0

The loop iterates over the array with both the index and the current value. For each iteration the difference between the current value and the previous value is calculated. This delta captures how much the cumulative sums must be adjusted when moving the window one step to the right.

for i, n in enumerate(nums):
    delta = n - prev

The left side contribution is increased by the product of the delta and the number of elements already processed (i). This reflects that each of those i elements is now farther from the current element by delta.

    left += delta * i

Conversely, the right side contribution is decreased by the product of the delta and the number of elements that remain to be processed (size - i). Those elements become closer to the current element by the same amount.

    right -= delta * (size - i)

The sum of the left and right contributions yields the total absolute difference for the current index, which is emitted by the generator.

    yield left + right

Finally, the previous value is updated to the current one so that the next iteration can compute the correct delta.

    prev = n

Edge Cases Handled

When the input list is empty, size becomes zero and right is the sum of an empty list, which is zero. The loop body never executes, and the generator produces no values, correctly representing the absence of any differences.

If the list contains a single element, the loop runs once with i equal to zero. The delta equals the element itself because prev starts at zero. The left contribution remains zero because i is zero, and the right contribution is reduced by delta * (size - i), which is delta * 1. The yielded value is left + right, which simplifies to zero, matching the fact that the absolute difference of an element with itself is zero.

The algorithm also works correctly for arrays that contain duplicate values. Since the delta between equal consecutive elements is zero, the left and right accumulators remain unchanged for those steps, and the yielded sum reflects the unchanged distance contributions.

Because the method relies only on arithmetic operations and does not perform any indexing beyond the current element, it gracefully handles very large integer values without risk of index errors.

Performance Optimizations

The implementation achieves linear time execution by avoiding nested loops. Instead of recomputing the sum of absolute differences from scratch for each index, it incrementally updates two aggregates (left and right). The use of the delta variable allows the algorithm to adjust these aggregates in constant time per iteration, leveraging the fact that the input is processed in order.

Maintaining a running total of the right side (right) by subtracting the appropriate amount each step eliminates the need to recompute the sum of the remaining elements. Similarly, the left side (left) is built up incrementally, avoiding repeated summations of the already-processed prefix.

The generator (yield) provides a memory-efficient way to produce results. Rather than constructing an auxiliary list of the same size as the input, the function yields each computed value on demand, which can be advantageous when the consumer processes the output sequentially or stops early.

Overall, the combination of a single pass, incremental updates, and lazy output delivers an efficient solution for the problem of computing sum of absolute differences across a sorted array.

Imagine a row of building blocks of different heights sitting on a table. The goal of this code is to look at each block one by one and calculate how much taller or shorter it is compared to all the other blocks combined.

To do this efficiently, the code first counts how many blocks there are and adds up all their heights. It keeps track of two groups of numbers, one for the blocks to the left and one for the blocks to the right.

As the code walks through the row block by block, it notices how much the height changes from one block to the next. It uses this change to update the total difference for the left side and the right side without having to re-count everything from the very beginning every single time. By adding these two totals together, it finds the final number for each position and shares it. This is like a smart shortcut for finding the total distance between every pair of blocks.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	JS	Java		Go	C#	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM							C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality