Sum of Absolute Differences in a Sorted Array: Prefix Sum Trick

You are given a sorted integer array nums, and you need to build an array result where result[i] equals the sum of |nums[i] - nums[j]| for all j != i. This is LeetCode 1685: Sum of Absolute Differences in a Sorted Array, a medium problem that teaches you how to exploit sorted order and prefix sums to collapse an O(n^2) computation into O(n).

The problem

For each index i, you need to compute the total absolute difference between nums[i] and every other element in the array. The brute force approach checks every pair, but the fact that the array is sorted gives you a powerful shortcut.

The brute force approach

The most direct solution uses two nested loops. For each index i, iterate through every other index j and accumulate |nums[i] - nums[j]|.

def getSumAbsoluteDifferences(nums):
    n = len(nums)
    result = []
    for i in range(n):
        total = 0
        for j in range(n):
            total += abs(nums[i] - nums[j])
        result.append(total)
    return result

This runs in O(n^2) time. For an array of length 100,000, that is 10 billion operations. You need something faster.

The key insight

Because nums is sorted in non-decreasing order, you know exactly which elements are smaller and which are larger than nums[i]. Every element to the left of index i satisfies nums[j] <= nums[i], so |nums[i] - nums[j]| simplifies to nums[i] - nums[j]. Every element to the right satisfies nums[j] >= nums[i], so the absolute value becomes nums[j] - nums[i].

This means you can split the sum into two halves. The left contribution is i * nums[i] - (sum of all elements before i). The right contribution is (sum of all elements after i) - (n - i - 1) * nums[i]. Both of these sub-expressions can be evaluated in O(1) if you precompute a prefix sum array.

Step-by-step walkthrough

Let's trace through nums = [2, 3, 5]. First, build the prefix sum array, then compute each result entry using the left and right formulas.

Each step performs a constant amount of arithmetic. After a single O(n) pass to build the prefix sum array, you compute every result value in O(1).

The code

def getSumAbsoluteDifferences(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    result = []
    for i in range(n):
        left = i * nums[i] - prefix[i]
        right = (prefix[n] - prefix[i + 1]) - (n - i - 1) * nums[i]
        result.append(left + right)
    return result

Here is what each piece does:

1. Build a prefix sum array of length n + 1. Entry prefix[i] holds the sum of the first i elements.
2. For each index i, compute the left contribution. There are i elements to the left, all of which are at most nums[i]. The sum of those elements is prefix[i], so the total difference is i * nums[i] - prefix[i].
3. Compute the right contribution. There are n - i - 1 elements to the right, all of which are at least nums[i]. Their sum is prefix[n] - prefix[i + 1], so the total difference is (prefix[n] - prefix[i + 1]) - (n - i - 1) * nums[i].
4. Add left and right together for result[i].

Complexity analysis

The prefix sum array takes O(n) to build and O(n) space. The result computation is a single O(n) pass. No nested loops, no sorting (the input is already sorted), and no hash maps.

The building blocks

Prefix sums on sorted arrays

A prefix sum array lets you compute the sum of any subarray in O(1). When the input is sorted, prefix sums become even more useful because you can reason about the relative sizes of elements by their positions. If j is to the left of i, you know nums[j] <= nums[i], and the prefix sum gives you their total without iterating.

This pattern appears in many problems. Any time you need to compute aggregates over portions of a sorted array (like sums, counts, or averages), prefix sums are the right tool.

Splitting absolute differences by sign

Absolute value expressions like |a - b| are hard to work with algebraically because they depend on which operand is larger. When you know the ordering in advance (because the array is sorted), you can drop the absolute value and replace it with a simple subtraction. This converts a piecewise expression into a clean arithmetic formula.

You will see this technique in problems involving distances on a number line, sorted arrays with pairwise comparisons, and geometric problems where coordinates are processed in order.

Edge cases

Before submitting, make sure your solution handles these:

• Single element: nums = [5]. There are no other elements, so result = [0].
• Two elements: nums = [1, 4]. Each element only compares against one other, so result = [3, 3].
• All same elements: nums = [3, 3, 3]. Every absolute difference is 0, so result = [0, 0, 0].
• Large values: Elements can be up to 10^4 and the array can have up to 10^5 entries. The prefix sums and products stay within standard 64-bit integer range, so no overflow issues in Python.
• Already computed prefix sum vs index mismatch: A common off-by-one error is confusing prefix[i] (sum of the first i elements, indices 0 through i-1) with prefix[i+1] (sum of the first i+1 elements). Double-check your indices.

From understanding to recall

You have seen how sorted order lets you drop the absolute value, and how a prefix sum array turns each half of the computation into O(1) arithmetic. The formula is compact: left = i * nums[i] - prefix[i], right = (prefix[n] - prefix[i+1]) - (n-i-1) * nums[i].

But compact formulas are easy to scramble under pressure. Was it i * nums[i] - prefix[i] or prefix[i] - i * nums[i]? Did you use prefix[i] or prefix[i+1] for the left side? These are the details that slip away without practice.

Spaced repetition fixes this. You write the prefix sum setup and the left/right formulas from scratch at increasing intervals. After a few rounds, the derivation is automatic. You see "sorted array, pairwise absolute differences" and the code flows out: build prefix, split by position, subtract. No hesitation.

The prefix sum trick is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Subarray Sum Equals K - Another prefix sum problem where precomputed sums unlock an O(n) solution
• Product of Array Except Self - Uses forward and backward passes (prefix and suffix products) to avoid nested loops
• Running Sum of 1D Array - The simplest prefix sum problem, a good warmup before tackling this one