Sum of Absolute Differences in a Sorted Array solution and explanation
IBM
Google
9 more videos on this problem
Sum of Absolute Differences in a Sorted Array - Leetcode 1685 - PythonNeetCodeIO · 12:08 · 13K views
Sum of Absolute Differences in a Sorted Array | Build Intuition | 2 Approaches | Leetcode - 1685codestorywithMIK · 31:12 · 6K views
Leetcode 1685. Sum of Absolute Differences in a Sorted ArrayFraz · 8:36 · 6K views
1685. Sum of Absolute Differences in a Sorted Array | Space - O(1)Aryan Mittal · 9:54 · 3K views
1685. Sum of Absolute Differences in a Sorted Array || LeetcodeAryan Mittal · 11:48 · 2K views
LeetCode 1685. Sum of Absolute Differences in a Sorted ArrayHappy Coding · 10:30 · 1K views
LeetCode 1685. Sum of Absolute Differences in a Sorted Array - Interview Prep Ep 113Fisher Coder · 21:02 · 903 views
✅ Sum of Absolute Differences in a Sorted Array - Two Pointers - Explained & Visualized -LeetCodeLeet Logics · 7:35 · 823 views
Sum of Absolute Differences in a Sorted Array- Leetcode 1685 - PythonTechError · 9:40 · 664 views
Solving LeetCode 1685 Sum of Absolute Differences in a Sorted Array | Prefix Sum ProblemCode Harmony · 12:02 · 414 views
The problem
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 <= 1051 <= 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.
def getSumAbsoluteDifferences(nums):
result = []
for i in range(len(nums)):
sum_diff = 0
for j in range(len(nums)):
sum_diff += abs(nums[i] - nums[j])
result.append(sum_diff)
return result
nums = [2, 3, 5]
print(getSumAbsoluteDifferences(nums))import java.util.Arrays;
public class Main {
public static int[] getSumAbsoluteDifferences(int[] nums) {
int n = nums.length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
sum += Math.abs(nums[i] - nums[j]);
}
result[i] = sum;
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 3, 5};
int[] result = getSumAbsoluteDifferences(nums);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <cmath>
#include <iostream>
std::vector<int> getSumAbsoluteDifferences(const std::vector<int>& nums) {
int n = nums.size();
std::vector<int> result(n);
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = 0; j < n; ++j) {
sum += std::abs(nums[i] - nums[j]);
}
result[i] = sum;
}
return result;
}
int main() {
std::vector<int> nums = {2, 3, 5};
std::vector<int> result = getSumAbsoluteDifferences(nums);
for (int r : result) {
std::cout << r << " ";
}
std::cout << std::endl;
return 0;
}function getSumAbsoluteDifferences(nums) {
let result = [];
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = 0; j < nums.length; j++) {
sum += Math.abs(nums[i] - nums[j]);
}
result.push(sum);
}
return result;
}
let nums = [2, 3, 5];
console.log(getSumAbsoluteDifferences(nums));#include <stdio.h>
#include <stdlib.h>
int* getSumAbsoluteDifferences(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
int* result = (int*)malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; i++) {
int sum = 0;
for (int j = 0; j < numsSize; j++) {
sum += abs(nums[i] - nums[j]);
}
result[i] = sum;
}
return result;
}
int main() {
int nums[] = {2, 3, 5};
int returnSize;
int* result = getSumAbsoluteDifferences(nums, 3, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
class Program {
static int[] GetSumAbsoluteDifferences(int[] nums) {
int n = nums.Length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
sum += Math.Abs(nums[i] - nums[j]);
}
result[i] = sum;
}
return result;
}
static void Main() {
int[] nums = { 2, 3, 5 };
int[] result = GetSumAbsoluteDifferences(nums);
Console.WriteLine(string.Join(" ", result));
}
}The Python solution utilizes two nested loops to compute the sum of absolute differences for each element. Each element's result is stored in a result list, which is returned at the end.
Time Complexity: O(n^2) due to the requirement to compare each element with every other element.
Space Complexity: O(n) for storing the results.
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 numbernums[j]contributes to|nums[i] - nums[j]|asnums[i] - nums[j]. - From right of
ito end, each numbernums[j]contributes asnums[j] - nums[i].
def getSumAbsoluteDifferences(nums):
n = len(nums)
left_sum = 0
right_sum = sum(nums)
result = [0] * n
for i in range(n):
right_sum -= nums[i]
result[i] = nums[i] * i - left_sum + right_sum - nums[i] * (n - i - 1)
left_sum += nums[i]
return result
nums = [2, 3, 5]
print(getSumAbsoluteDifferences(nums))import java.util.Arrays;
public class Main {
public static int[] getSumAbsoluteDifferences(int[] nums) {
int n = nums.length, leftSum = 0, rightSum = 0;
int[] result = new int[n];
for (int num : nums) rightSum += num;
for (int i = 0; i < n; i++) {
rightSum -= nums[i];
result[i] = nums[i] * i - leftSum + rightSum - nums[i] * (n - i - 1);
leftSum += nums[i];
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 3, 5};
int[] result = getSumAbsoluteDifferences(nums);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <iostream>
std::vector<int> getSumAbsoluteDifferences(const std::vector<int>& nums) {
int n = nums.size(), leftSum = 0, rightSum = 0;
std::vector<int> result(n, 0);
for (int num : nums) rightSum += num;
for (int i = 0; i < n; ++i) {
rightSum -= nums[i];
result[i] = nums[i] * i - leftSum + rightSum - nums[i] * (n - i - 1);
leftSum += nums[i];
}
return result;
}
int main() {
std::vector<int> nums = {2, 3, 5};
std::vector<int> result = getSumAbsoluteDifferences(nums);
for (int r : result) {
std::cout << r << " ";
}
return 0;
}function getSumAbsoluteDifferences(nums) {
let n = nums.length;
let result = new Array(n).fill(0);
let leftSum = 0, rightSum = nums.reduce((a, b) => a + b, 0);
for (let i = 0; i < n; i++) {
rightSum -= nums[i];
result[i] = nums[i] * i - leftSum + rightSum - nums[i] * (n - i - 1);
leftSum += nums[i];
}
return result;
}
let nums = [2, 3, 5];
console.log(getSumAbsoluteDifferences(nums));#include <stdio.h>
#include <stdlib.h>
int* getSumAbsoluteDifferences(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
int* result = (int*)malloc(numsSize * sizeof(int));
int leftSum = 0, rightSum = 0;
for (int i = 0; i < numsSize; ++i) rightSum += nums[i];
for (int i = 0; i < numsSize; ++i) {
rightSum -= nums[i];
result[i] = nums[i] * i - leftSum + rightSum - nums[i] * (numsSize - i - 1);
leftSum += nums[i];
}
return result;
}
int main() {
int nums[] = {2, 3, 5};
int returnSize;
int* result = getSumAbsoluteDifferences(nums, 3, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
class Program {
static int[] GetSumAbsoluteDifferences(int[] nums) {
int n = nums.Length, leftSum = 0, rightSum = 0;
int[] result = new int[n];
foreach (int num in nums) rightSum += num;
for (int i = 0; i < n; i++) {
rightSum -= nums[i];
result[i] = nums[i] * i - leftSum + rightSum - nums[i] * (n - i - 1);
leftSum += nums[i];
}
return result;
}
static void Main() {
int[] nums = { 2, 3, 5 };
int[] result = GetSumAbsoluteDifferences(nums);
Console.WriteLine(string.Join(" ", result));
}
}By leveraging prefix sums in Python, the result for each index is calculated in a single pass through the array using the elapsed prefix totals and consequently derived equations.
Time Complexity: O(n).
Space Complexity: O(n) required to hold the computed results.
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).
function getSumAbsoluteDifferences(nums: number[]): number[] {
const s = nums.reduce((a, b) => a + b);
let t = 0;
const n = nums.length;
const ans = new Array(n);
for (let i = 0; i < n; ++i) {
const v = nums[i] * i - t + s - t - nums[i] * (n - i);
ans[i] = v;
t += nums[i];
}
return ans;
}func getSumAbsoluteDifferences(nums []int) (ans []int) {
var s, t int
for _, x := range nums {
s += x
}
for i, x := range nums {
v := x*i - t + s - t - x*(len(nums)-i)
ans = append(ans, v)
t += x
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: |
| Optimized Using Prefix Sums | Time Complexity: |
| Summation + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Pairwise Calculation | O(n²) | O(1) | Useful for understanding the problem definition or when input size is very small |
| Prefix Sum Optimization | O(n) | O(n) | Best choice when the array is sorted and you need a scalable solution |
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.