728x90
https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
total_sum = sum(nums)
left_sum = 0
res = []
for i , n in enumerate(nums):
right_sum = total_sum - n - left_sum
left_size, right_size = i , len(nums) - i -1
res.append(
left_size * n - left_sum +
right_sum - right_size * n
)
left_sum += n
return res
rather than just iterating arrays and subtract individually
compute prefix sum (left sum) and postfix sum (right sum)
and calculating result like above
728x90
'Algorithm > NeetCode' 카테고리의 다른 글
Convert an Array Into a 2D Array With Conditions (0) | 2024.11.22 |
---|---|
Design a Food Rating System (0) | 2024.11.21 |
Majority Element II (0) | 2024.11.19 |
Champagne Tower (0) | 2024.11.18 |
Minimum Penalty for a Shop (0) | 2024.11.17 |