<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. There exists an array <code>arr</code> of length <code>nums.length</code>, where <code>arr[i]</code> is the sum of <code>|i - j|</code> over all <code>j</code> such that <code>nums[j] == nums[i]</code> and <code>j != i</code>. If there is no such <code>j</code>, set <code>arr[i]</code> to be <code>0</code>.</p>

<p>Return <em>the array </em><code>arr</code><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,1,1,2]
<strong>Output:</strong> [5,0,3,4,0]
<strong>Explanation:</strong> 
When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5. 
When i = 1, arr[1] = 0 because there is no other index with value 3.
When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3. 
When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4. 
When i = 4, arr[4] = 0 because there is no other index with value 2. 

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,5,3]
<strong>Output:</strong> [0,0,0]
<strong>Explanation:</strong> Since each element in nums is distinct, arr[i] = 0 for all i.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Note:</strong> This question is the same as <a href="https://leetcode.com/problems/intervals-between-identical-elements/description/" target="_blank"> 2121: Intervals Between Identical Elements.</a></p>

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        '''
    compute arr(a(i)) where pos = a(i)
    1) a(i) - a(k)  = (a(i) - a(0)) - (a(k) - a(0)) for 0 <= k <= i
    2) a(k) - a(i)  = (a(k) - a(0)) - (a(i) - a(0)) for i + 1 <= k < = m - 1
    define
        pre_sum(i) = a(0) + a(1) + ... + a(i)
    so
    arr(a(i)) = a(i) - a(0) + a(i) - a(1) ... + a(i) - a(i - 1) + a(i + 1) - a(i) .. + a(m - 1) - a(i)
              = (i - 1 - 0 + 1) * a(i) - (m - 1 - (i + 1) + 1) * a(i) - (a(0) + a(1) + ... + a(i - 1)) + ((a(i + 1) + a(i + 2) ... + a(m - 1))
              = i * a(i) - (m - i - 1) * a(i) - pre_sum(i - 1) + pre_sum(m - 1) - pre_sum(i)
        '''
        index = {}
        for i, v in enumerate(nums):
            if v not in index:
                index[v] = []
            index[v].append(i)
        arr = [0] * len(nums)
        for v in index:
            pos_list = index[v]
            m = len(pos_list)
            if m < 2:
                continue
            pre_sum = [0]
            for pos in pos_list:
                pre_sum.append(pre_sum[-1] + pos)
            
            print(pos_list)
            print(pre_sum)
            for i, pos in enumerate(pos_list):
                arr[pos] = i * pos - (m - i - 1) * pos
                arr[pos] -= pre_sum[i] # pre_sum for 0, ... i - 1
                arr[pos] += pre_sum[m] - pre_sum[i + 1]
        return arr
585