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] <= 104The 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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) where n is the length of the array.
Space Complexity: O(n) for the result array.
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:
i, each number nums[j] contributes to |nums[i] - nums[j]| as nums[i] - nums[j].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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as each element is processed only twice.
Space Complexity: O(n) to store the result.
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: |
| Optimized Using Prefix Sums | Time Complexity: |
Sum of Absolute Differences in a Sorted Array - Leetcode 1685 - Python • NeetCodeIO • 10,981 views views
Watch 9 more video solutions →Practice Sum of Absolute Differences in a Sorted Array with our built-in code editor and test cases.
Practice on FleetCode