NeetCode #142LC-1685MediumArrays & Hashing
← Back to All Problems#142 · #1685 · Sum of Absolute Differences in a Sorted Array(有序数组中差绝对值之和)
📌 Problem Statement & Constraints
Given an array
nums sorted in non-decreasing order, return an array where result[i] is the sum of |nums[i] - nums[j]| over all j. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^4.💡 Core Algorithmic Approaches
- The naive double loop is O(n^2). Prefix sums make each index O(1).
- For index
i, the elements to the left are all<= nums[i], so their total contribution isi * nums[i] - prefix[i]. - The elements to the right are all
>= nums[i], contributing(prefix[n] - prefix[i+1]) - (n - 1 - i) * nums[i]. - Adding the two gives
result[i]. This works precisely because the array is sorted.
💻 Benchmark Python3 Implementation
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
n = len(nums)
pref = [0] * (n + 1)
for i, x in enumerate(nums):
pref[i + 1] = pref[i] + x
res = []
for i, x in enumerate(nums):
left = i * x - pref[i] # sum of x - nums[j] for j < i
right = (pref[n] - pref[i + 1]) - (n - 1 - i) * x # sum of nums[j] - x for j > i
res.append(left + right)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to build the prefix sums and one pass to compute the answers.
💾 Space Complexity
O(n) for the prefix array (O(1) extra if computed on the fly with a running total).
⚠️ Interview Pitfalls & Follow-ups
- Ignoring the sortedness: the prefix-sum trick relies on all left elements being
<= xand all right elements being>= x; without sorting, absolute values would have to be handled per element. - Wrong count on the right: there are
n - 1 - ielements to the right, notn - i. - Using the unsorted input: the problem guarantees non-decreasing order, so no sort is needed -- but if you sorted, the output order would no longer correspond to the input.
- Computing with
absin a nested loop: O(n^2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.