#1685

Medium

LeetCode Problem Workspace

Sum of Absolute Differences in a Sorted Array

Calculate the sum of absolute differences between each element and others in a sorted array efficiently.

Problem Statement

You are given an integer array nums sorted in non-decreasing order. Your task is to build and return a new integer array result, where result[i] is the summation of absolute differences between nums[i] and all other elements in the array.

In simpler terms, result[i] is the sum of |nums[i] - nums[j]| for all j != i where 0 <= j < nums.length. You need to compute this efficiently for large arrays.

Examples

Example 1

Input: nums = [2,3,5]

Output: [4,3,5]

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]

Example details omitted.

Constraints

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

Solution Approach

Utilizing Absolute Difference Property

The absolute difference |a - b| can be simplified using the formula max(a, b) - min(a, b). This property helps to calculate differences without explicitly using nested loops.

Prefix Sum Optimization

By calculating prefix sums, we can efficiently compute the summation of absolute differences. This allows us to avoid the time complexity of nested loops, reducing it to linear time.

Efficient Array Traversal

Traversing the array and calculating results based on previous sums avoids redundant calculations, leveraging the sorted nature of the array to further speed up the process.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) due to the use of prefix sums and array traversal, which allows for direct computation of each element's result without nested loops. The space complexity is O(1) since no extra space beyond a few variables is needed.

What Interviewers Usually Probe

Look for understanding of how absolute differences work in sorted arrays.
Check for familiarity with prefix sums and how they can optimize summation problems.
Evaluate the candidate’s ability to optimize an otherwise brute-force solution.

Common Pitfalls or Variants

Common pitfalls

Not leveraging the sorted array property, resulting in unnecessary nested loops.
Incorrect use of prefix sums or failure to update them correctly as the array is traversed.
Failing to optimize the solution for larger arrays, which may lead to time limit exceed errors.

Follow-up variants

Instead of absolute differences, calculate the sum of squared differences between each element and others.
Consider cases where the array is not sorted, and the time complexity will increase.
Calculate differences based on a dynamic range of indices rather than all elements in the array.

FAQ

What is the time complexity of the Sum of Absolute Differences in a Sorted Array?

The time complexity is O(n), achieved by using prefix sums to avoid nested loops.

How do prefix sums help in solving the Sum of Absolute Differences problem?

Prefix sums allow for efficient summation of absolute differences by computing cumulative sums as you traverse the array.

How does the sorted property of the array help in solving the problem?

The sorted property allows for simplification of the absolute difference calculation, making it possible to calculate results in linear time.

What is a common mistake when solving this problem?

A common mistake is not taking advantage of the sorted array property, resulting in a solution with higher time complexity.

What are some variations of the Sum of Absolute Differences problem?

Variations include calculating squared differences instead of absolute differences or solving the problem for unsorted arrays.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        ans = []
        s, t = sum(nums), 0
        for i, x in enumerate(nums):
            v = x * i - t + s - t - x * (len(nums) - i)
            ans.append(v)
            t += x
        return ans

Continue Practicing

#1588 sum of all odd length subarrays #1524 number of sub arrays with odd sum #1862 sum of floored pairs