LeetCode 1685 - Sum of Absolute Differences in a Sorted Array

The problem gives us a sorted integer array nums, arranged in non-decreasing order. For every index i, we must compute t

leetcodemediumarraymathprefix-sum

LeetCode Problem 1685

Difficulty: 🟡 Medium
Topics: Array, Math, Prefix Sum

Solution

Problem Understanding

The problem gives us a sorted integer array nums, arranged in non-decreasing order. For every index i, we must compute the total sum of absolute differences between nums[i] and every other element in the array.

Formally, for each position i:

$$result[i] = \sum_{j=0}^{n-1} |nums[i] - nums[j]|$$

The output must be an array of the same length where each element contains this computed value.

The key detail is that the array is already sorted. This changes the problem significantly because absolute differences become predictable depending on whether elements are to the left or right of the current position.

For example, if:

nums = [1,4,6,8,10]

then for index 2, the value is 6, and:

|6-1| + |6-4| + |6-6| + |6-8| + |6-10|
= 5 + 2 + 0 + 2 + 4
= 13

The constraints are important:

  • 2 <= nums.length <= 10^5
  • nums is sorted
  • Values are positive integers

An array size of 10^5 immediately tells us that an O(n^2) solution will be too slow. A quadratic solution would require up to:

$$10^5 \times 10^5 = 10^{10}$$

operations, which is far beyond acceptable limits.

The sorted property is the crucial observation. Since the array is ordered, we know:

  • Every element to the left of nums[i] is less than or equal to it
  • Every element to the right is greater than or equal to it

This allows us to remove the absolute value operation and compute contributions mathematically using prefix sums.

Some important edge cases include:

  • Arrays with only two elements
  • Arrays where all values are equal
  • Arrays with repeated numbers
  • Strictly increasing arrays
  • Large arrays where efficiency matters

The problem guarantees the array is sorted, so we do not need to handle unsorted input.

Approaches

Brute Force Approach

The most straightforward solution is to compute every absolute difference directly.

For each index i, we iterate through the entire array and calculate:

abs(nums[i] - nums[j])

for every j.

We then sum all these values and store the result.

This works because it directly follows the problem definition. Every pairwise difference is explicitly calculated.

However, this approach requires two nested loops:

  • Outer loop over all elements
  • Inner loop over all elements again

That leads to O(n^2) time complexity.

With n = 10^5, this becomes far too slow.

Optimal Prefix Sum Approach

The key insight comes from the sorted nature of the array.

Suppose we are processing nums[i].

Since the array is sorted:

  • All elements before index i are smaller or equal
  • All elements after index i are larger or equal

Therefore:

For elements on the left:

$$|nums[i] - nums[j]| = nums[i] - nums[j]$$

For elements on the right:

$$|nums[i] - nums[j]| = nums[j] - nums[i]$$

We can compute both parts separately.

If we know:

  • The sum of all elements to the left
  • The sum of all elements to the right

then we can calculate the contribution in constant time.

Using prefix sums allows us to obtain these sums efficiently.

For index i:

Left contribution:

$$nums[i] \times i - leftSum$$

Right contribution:

$$rightSum - nums[i] \times (n-i-1)$$

Adding them gives the final answer for index i.

This reduces the total complexity to O(n).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) excluding output Directly computes every absolute difference
Optimal O(n) O(1) excluding output Uses prefix sums and sorted property

Algorithm Walkthrough

  1. Compute the total sum of the array.

We first calculate the sum of all elements. This allows us to efficiently determine the sum of elements to the right of the current index during iteration. 2. Initialize a running prefix sum.

We maintain left_sum, which stores the sum of all elements before the current index. 3. Iterate through the array.

For each index i, let the current value be num. 4. Compute the left contribution.

Since all elements on the left are less than or equal to num, the total difference contribution from the left side is:

$$num \times i - left_sum$$

Here:

  • num * i represents the sum if all left elements were equal to num
  • Subtracting left_sum gives the total difference
  1. Compute the right contribution.

The sum of elements to the right is:

$$total_sum - left_sum - num$$

Let this be right_sum.

Since all right-side elements are greater than or equal to num, their contribution is:

$$right_sum - num \times (n-i-1)$$ 6. Add both contributions.

The final result for index i is:

$$left_contribution + right_contribution$$ 7. Update the prefix sum.

Add num to left_sum before moving to the next index.

Why it works

The algorithm works because the array is sorted. This guarantees that for any index i:

  • Every left element contributes nums[i] - nums[j]
  • Every right element contributes nums[j] - nums[i]

By grouping these mathematically instead of computing each pair individually, we transform many repeated calculations into simple arithmetic using prefix sums. Every element’s total contribution is computed exactly once, giving a correct and efficient solution.

Python Solution

from typing import List

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        total_sum = sum(nums)

        result = [0] * n
        left_sum = 0

        for i, num in enumerate(nums):
            right_sum = total_sum - left_sum - num

            left_contribution = num * i - left_sum
            right_contribution = right_sum - num * (n - i - 1)

            result[i] = left_contribution + right_contribution

            left_sum += num

        return result

The implementation begins by calculating the total sum of the array. This allows us to determine the sum of the right-side elements during iteration without needing another data structure.

The left_sum variable tracks the cumulative sum of elements before the current index.

Inside the loop:

  • right_sum is computed by subtracting the current element and left_sum from the total sum.
  • left_contribution calculates how much all left elements contribute to the absolute difference.
  • right_contribution calculates how much all right elements contribute.

These two values are added together and stored in the result array.

Finally, we update left_sum so the next iteration has the correct prefix information.

The algorithm processes each element exactly once, giving linear time complexity.

Go Solution

func getSumAbsoluteDifferences(nums []int) []int {
	n := len(nums)

	totalSum := 0
	for _, num := range nums {
		totalSum += num
	}

	result := make([]int, n)
	leftSum := 0

	for i, num := range nums {
		rightSum := totalSum - leftSum - num

		leftContribution := num*i - leftSum
		rightContribution := rightSum - num*(n-i-1)

		result[i] = leftContribution + rightContribution

		leftSum += num
	}

	return result
}

The Go implementation follows the exact same logic as the Python solution.

The main differences are language-specific:

  • Go requires explicit slice allocation using make.
  • There is no built-in sum function for slices, so we compute totalSum manually.
  • Integer arithmetic is safe under the given constraints because the maximum possible sum fits comfortably within Go's int range.

Since the input length is guaranteed to be at least 2, there is no need for special nil or empty handling.

Worked Examples

Example 1

nums = [2,3,5]

Initial values:

total_sum = 10
left_sum = 0
i num left_sum right_sum left_contribution right_contribution result[i]
0 2 0 8 2×0 - 0 = 0 8 - 2×2 = 4 4
1 3 2 5 3×1 - 2 = 1 5 - 3×1 = 2 3
2 5 5 0 5×2 - 5 = 5 0 - 5×0 = 0 5

Final result:

[4,3,5]

Example 2

nums = [1,4,6,8,10]

Initial values:

total_sum = 29
left_sum = 0
i num left_sum right_sum left_contribution right_contribution result[i]
0 1 0 28 0 28 - 1×4 = 24 24
1 4 1 24 4×1 - 1 = 3 24 - 4×3 = 12 15
2 6 5 18 6×2 - 5 = 7 18 - 6×2 = 6 13
3 8 11 10 8×3 - 11 = 13 10 - 8×1 = 2 15
4 10 19 0 10×4 - 19 = 21 0 21

Final result:

[24,15,13,15,21]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once
Space O(1) excluding output Only a few extra variables are used

The algorithm makes a single pass through the array after computing the total sum. Every operation inside the loop is constant time arithmetic. No nested loops or auxiliary data structures are required.

The output array itself is not counted toward auxiliary space complexity because it is required by the problem.

Test Cases

from typing import List

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        total_sum = sum(nums)

        result = [0] * n
        left_sum = 0

        for i, num in enumerate(nums):
            right_sum = total_sum - left_sum - num

            left_contribution = num * i - left_sum
            right_contribution = right_sum - num * (n - i - 1)

            result[i] = left_contribution + right_contribution

            left_sum += num

        return result

sol = Solution()

assert sol.getSumAbsoluteDifferences([2,3,5]) == [4,3,5]  # basic example
assert sol.getSumAbsoluteDifferences([1,4,6,8,10]) == [24,15,13,15,21]  # larger example

assert sol.getSumAbsoluteDifferences([1,1]) == [0,0]  # all equal elements
assert sol.getSumAbsoluteDifferences([1,2]) == [1,1]  # minimum size array
assert sol.getSumAbsoluteDifferences([1,1,1,1]) == [0,0,0,0]  # repeated values

assert sol.getSumAbsoluteDifferences([1,2,3,4,5]) == [10,7,6,7,10]  # strictly increasing
assert sol.getSumAbsoluteDifferences([5,5,5,10]) == [5,5,5,15]  # duplicates with larger tail
assert sol.getSumAbsoluteDifferences([1,10,100]) == [108,99,189]  # large gaps between values

assert sol.getSumAbsoluteDifferences([0,0,0]) == [0,0,0]  # all zeros

Test Case Summary

Test Why
[2,3,5] Validates the first provided example
[1,4,6,8,10] Validates the second provided example
[1,1] Smallest valid size with equal values
[1,2] Smallest valid increasing array
[1,1,1,1] Ensures duplicates are handled correctly
[1,2,3,4,5] Tests normal strictly increasing sequence
[5,5,5,10] Tests repeated values plus outlier
[1,10,100] Tests large numerical gaps
[0,0,0] Tests zero-difference behavior

Edge Cases

All Elements Are Equal

If every value in the array is identical, every absolute difference is zero.

For example:

[5,5,5,5]

Every element produces:

|5-5| = 0

A buggy implementation might incorrectly compute negative values or mishandle duplicate counts. This solution works correctly because both the left and right contribution formulas naturally evaluate to zero.

Minimum Array Size

The smallest allowed input size is 2.

For example:

[1,2]

This is important because some implementations accidentally assume there are elements on both sides of every index. Our implementation safely handles edge positions because:

  • Left contribution becomes zero for index 0
  • Right contribution becomes zero for the last index

No special-case logic is required.

Arrays With Repeated Values

Repeated numbers can cause logical mistakes if the algorithm incorrectly assumes strict ordering.

For example:

[1,1,3,3]

The sorted-array property still holds because the array is non-decreasing, not strictly increasing.

The formulas continue to work because equal elements contribute zero difference naturally.

Large Inputs

With up to 10^5 elements, performance matters significantly.

A brute-force solution would timeout due to quadratic complexity. The prefix sum approach processes each element once and uses only constant extra memory, making it efficient enough for the largest allowed inputs.