Algorithm/NeetCode

Sum of Absolute Differences in a Sorted Array

Tony Lim 2024. 11. 20. 17:45
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