# Prefix Sum
###### tags: `Algorithm`

## Tutorial and example
[Concept with Leetcode examples](https://blog.csdn.net/ch_609583349/article/details/106423315)

## lc 2615

from collections import defaultdict
from typing import List

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n

        # pass 1: contributions from the left (previous same values)
        cnt = defaultdict(int)
        ssum = defaultdict(int)  # sum of indices
        for i, x in enumerate(nums):
            ans[i] += i * cnt[x] - ssum[x]
            cnt[x] += 1
            ssum[x] += i

        # pass 2: contributions from the right (later same values)
        cnt.clear()
        ssum.clear()
        for i in range(n - 1, -1, -1):
            x = nums[i]
            ans[i] += ssum[x] - i * cnt[x]
            cnt[x] += 1
            ssum[x] += i

        return ans

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        """
        {
            "value": "array of index"
        }
        {
            "1": (number of indices, prefix sum)
        }
        
        # Solution1 (brute force)
        # build a map for recording same value indexes/indices
        # for each indexes run a double loop to get distance sum for each index
        # [0,2][0,3], [2,0][2,3], [3,0][3,2] O(n^2)
        
        # O(n)
        # loop twice (one forward one backward)
        # prefix_sum = sum of all the prefix indexes 
        # half_distance = current_index * num of prefix indexed - prefix_sum
        
        # forward
        [0, 2, 3]
        0: 0 
        2: 2 * 1 - 0 = 2
        3: 3 * 2 - 2 = 4     (|3-0| + |3-2|)
        # backward
        3: 0
        2: |2 * 1 - 3| = 1
        0: |0 * 2 - 5| = 5
        # [5,0,3,4,0]
        0: 5 + 0 = 5
        2: 2 + 1 = 3
        3: 4 + 0 = 4
        
        sum(|i - j|)     N number of j
        |N * i - sum(j)|
        """
        
        n = len(nums)
        result = [0] * n
        
        prefix_sum = dict() #  "value": (number of indices, prefix sum) 
        
        # forward
        # [0, 2, 3]
        # 0: 0 
        # 2: 2 * 1 - 0 = 2
        # 3: 3 * 2 - 2 = 4     (|3-0| + |3-2|)
        for i in range(n):
            if nums[i] not in prefix_sum:
                prefix_sum[nums[i]] = (1, i)
            else:
                seen_same_value_num, seen_same_value_index_sum = prefix_sum[nums[i]]
                result[i] += abs(seen_same_value_num * i - seen_same_value_index_sum)
                prefix_sum[nums[i]] = (seen_same_value_num + 1, seen_same_value_index_sum + i)
        
        # backward
        # 3: 0
        # 2: |2 * 1 - 3| = 1
        # 0: |0 * 2 - 5| = 5
        prefix_sum = dict() 
        for i in range(n-1, -1, -1):
            if nums[i] not in prefix_sum:
                prefix_sum[nums[i]] = (1, i) # result not updating -> 0
            else:
                seen_same_value_num, seen_same_value_index_sum = prefix_sum[nums[i]]
                result[i] += abs(seen_same_value_num * i - seen_same_value_index_sum)
                prefix_sum[nums[i]] = (seen_same_value_num + 1, seen_same_value_index_sum + i)
                
        return result