Skip to content

Distance Sum

Table of Contents

1685. Sum of Absolute Differences in a Sorted Array

1685. Sum of Absolute Differences in a Sorted Array - Python Solution
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]

2615. Sum of Distances

2602. Minimum Operations to Make All Array Elements Equal

2968. Apply Operations to Maximize Frequency Score

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, sliding window, sorting, prefix sum

1703. Minimum Adjacent Swaps for K Consecutive Ones

3086. Minimum Moves to Pick K Ones

3422. Minimum Operations to Make Subarray Elements Equal

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, math, sliding window, heap priority queue

Comments