⚡Flashcard Drill➔
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

  1. The naive double loop is O(n^2). Prefix sums make each index O(1).
  2. For index i, the elements to the left are all <= nums[i], so their total contribution is i * nums[i] - prefix[i].
  3. The elements to the right are all >= nums[i], contributing (prefix[n] - prefix[i+1]) - (n - 1 - i) * nums[i].
  4. 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 <= x and 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 - i elements to the right, not n - 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 abs in 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems