Skip to main content
Talentd

Sum of Absolute Differences in a Sorted Array - Solution & Explanation

MediumArrayMathPrefix Sum18 min readAsked at: Amazon, Meta, IBM +1
Practice this problem

Problem Statement

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).

 

Example 1:

Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.

Example 2:

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= nums[i + 1] <= 104

Approach Overview

Problem Overview: You receive a sorted integer array nums. For every index i, compute the sum of |nums[i] - nums[j]| for all other elements. Because the array is already sorted, values to the left are always smaller and values to the right are always larger. That ordering removes the need to compute absolute values individually.

Approach 1: Naive Pairwise Calculation (O(n²) time, O(1) space)

Iterate through each index i and compute the sum of absolute differences with every other element. This means a nested loop: the outer loop fixes nums[i], while the inner loop accumulates |nums[i] - nums[j]| for all j. The method uses only constant extra memory but performs n * n operations. It works for any array and clearly demonstrates the definition of the problem, but it becomes too slow when n grows large.

Approach 2: Prefix Sum Optimization (O(n) time, O(n) space)

The sorted property lets you separate contributions from the left and right sides. For index i, all elements before it are smaller. Their total difference equals nums[i] * i - leftSum. All elements after it are larger, contributing rightSum - nums[i] * (n - i - 1). Maintain prefix sums to quickly compute leftSum and derive rightSum from the total array sum. This removes the inner loop entirely and reduces the problem to a single pass.

The key insight: instead of computing each absolute difference separately, aggregate them using arithmetic derived from ordering. Prefix sums store cumulative totals so each index can evaluate both sides in constant time. This pattern appears frequently in problems involving cumulative distances or cost aggregation.

Conceptually, the algorithm works like this: compute the total sum, iterate once through the array, maintain a running prefix sum, and use simple multiplication to determine how much each side contributes. The final answer for each position is the sum of the left contribution and the right contribution.

Problems like this commonly combine Array traversal with Prefix Sum precomputation and a bit of arithmetic reasoning from Math. Recognizing that the array is sorted is the turning point that enables the linear solution.

Recommended for interviews: Interviewers expect the prefix sum approach. The brute force solution shows you understand the definition of absolute differences, but the optimized O(n) method demonstrates that you recognize patterns in sorted arrays and know how to convert repeated calculations into prefix-sum formulas.

Approach 1: Naive Approach

The naive approach involves calculating the summation of absolute differences directly for each element. For each element `nums[i]` in the array, iterate through every other element `nums[j]` and accumulate the absolute difference `|nums[i] - nums[j]|`. This results in a straightforward solution but with a time complexity of O(n^2) due to the nested loops.

This C solution initializes an array to store the results. For each element in the input array, it calculates the sum of absolute differences by iterating through the entire array and applying the abs function. The result for each element is stored in the result array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) where n is the length of the array.
Space Complexity: O(n) for the result array.

Try this approach in the editor →

Approach 2: Optimized Using Prefix Sums

To optimize the solution, use prefix sums to reduce redundant calculations. Compute prefix sums `leftSum` and `rightSum` to capture cumulative totals on each side of the current index. For each nums[i], compute the contribution using:

  • From left to i, each number nums[j] contributes to |nums[i] - nums[j]| as nums[i] - nums[j].
  • From right of i to end, each number nums[j] contributes as nums[j] - nums[i].

This C implementation uses cumulative `leftSum` and `rightSum` to keep track of elements processed. By adjusting these sums and using the formula, we efficiently calculate the results in O(n) time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) as each element is processed only twice.
Space Complexity: O(n) to store the result.

Try this approach in the editor →

Approach 3: Summation + Enumeration

First, we calculate the sum of all elements in the array nums, denoted as s. We use a variable t to record the sum of the elements that have been enumerated so far.

Next, we enumerate nums[i]. Then ans[i] = nums[i] times i - t + s - t - nums[i] times (n - i). After that, we update t, i.e., t = t + nums[i]. We continue to enumerate the next element until all elements are enumerated.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptJavaScriptC#

Python

Java

C++

Go

TypeScript

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Approach

Time Complexity: O(n^2) where n is the length of the array.
Space Complexity: O(n) for the result array.

Optimized Using Prefix Sums

Time Complexity: O(n) as each element is processed only twice.
Space Complexity: O(n) to store the result.

Summation + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Pairwise CalculationO(n²)O(1)Useful for understanding the problem definition or when input size is very small
Prefix Sum OptimizationO(n)O(n)Best choice when the array is sorted and you need a scalable solution

Video Solution

Sum of Absolute Differences in a Sorted Array - Leetcode 1685 - Python • NeetCodeIO • 13,209 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Absolute Differences in a Sorted Array easy or hard?
The problem is typically rated Medium because the brute force idea is straightforward but the efficient solution requires recognizing how sorting allows absolute differences to be simplified into prefix-sum formulas.
Sum of Absolute Differences in a Sorted Array Python/Java solution
Most implementations iterate once through the array while maintaining a prefix sum and total sum. The same formula works across languages like Python, Java, C++, and C#. Each index computes its result using arithmetic based on how many elements exist on the left and right sides.
How to solve Sum of Absolute Differences in a Sorted Array in O(n)?
First compute the total sum of the array and maintain a running prefix sum while iterating. For index i, calculate the left contribution as nums[i] * i minus the prefix sum. Compute the right contribution as (totalSum - prefixSum - nums[i]) minus nums[i] * (n - i - 1). Adding both values gives the answer for that index in constant time.
What is the best approach for Sum of Absolute Differences in a Sorted Array?
The optimal approach uses prefix sums and the sorted property of the array. For each index, compute the contribution from elements on the left and right using arithmetic formulas instead of calculating every absolute difference. This reduces the complexity from O(n²) to O(n) time with O(n) auxiliary space.
Is Sum of Absolute Differences in a Sorted Array asked at Google/Amazon/Meta?
Array prefix-sum problems with mathematical transformations frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. This problem tests recognition of sorted array properties and the ability to reduce repeated calculations using prefix sums.
What data structure is used in Sum of Absolute Differences in a Sorted Array?
The main structures are arrays and prefix sums. A prefix sum array or running cumulative sum stores the total of elements seen so far, allowing constant-time computation of left-side contributions for each index.
What is the time complexity of Sum of Absolute Differences in a Sorted Array?
The brute force solution runs in O(n²) time because it compares each element with every other element. The optimized solution runs in O(n) time by using prefix sums to aggregate differences in constant time for each index. Space complexity is typically O(n) if a prefix array is stored.

Ready to solve this problem?

Practice Sum of Absolute Differences in a Sorted Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays