Distance Sum¶
Table of Contents¶
- 1685. Sum of Absolute Differences in a Sorted Array (Medium)
- 2615. Sum of Distances (Medium)
- 2602. Minimum Operations to Make All Array Elements Equal (Medium)
- 2968. Apply Operations to Maximize Frequency Score (Hard)
- 1703. Minimum Adjacent Swaps for K Consecutive Ones (Hard)
- 3086. Minimum Moves to Pick K Ones (Hard)
- 3422. Minimum Operations to Make Subarray Elements Equal (Medium) 👑
1685. Sum of Absolute Differences in a Sorted Array¶
from typing import List
# Prefix Sum
def getSumAbsoluteDifferences(nums: List[int]) -> List[int]:
n = len(nums)
totalSum = sum(nums)
prefixSum = 0
res = [0 for _ in range(n)]
for i in range(n):
leftSum = prefixSum
rightSum = totalSum - prefixSum - nums[i]
leftCount = i
rightCount = n - i - 1
res[i] = (nums[i] * leftCount - leftSum) + (
rightSum - nums[i] * rightCount
)
prefixSum += nums[i]
return res
nums = [1, 4, 6, 8, 10]
print(getSumAbsoluteDifferences(nums)) # [24, 15, 13, 15, 21]