<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:
    # [1 3 1 1 2]
    # [2 + 3, 0]
    # [5 0 2 3 0]
    # fill in left to righ
    # if we have an equality, add |i - j| to both
    # O(N^2)
    # two parts:
    # find all the other indeces where each number occurs
    # |i - j_1| + |i - j_2| + /// + 
    # = (i+j_2+j_3) - 3*i
    # = j_2 + j_3 - 2 * i
    # = 5
    # the sum of all other indeces - 2 * 
    # find all the occurences to the left and to the right?
    # say j_1, j_2, ... j_m are to the left and k_1, k_2, ..., k_n are to the right
    # i - j_1 + i - j_2 + ... + i - j_m + k_1 - i + k_2 - i + ... + k_n
    # = m * i - (j_1 + ... + j_2 + j_m) + (k_1 + ... k_n) - n* i
    # = (m - n) * i - (sum of indeces to the left) + (sum of indeces to the right)
    # m = number of indeces to the left
    # n = number of indeces to the right
    def distance(self, nums: List[int]) -> List[int]:
        length = len(nums)
        res = [0] * length
        leftSum = defaultdict(int)
        rightSum = defaultdict(int)
        leftCount = defaultdict(int)
        rightCount = defaultdict(int)

        for i in range(length):
            rightSum[nums[i]] += i
            rightCount[nums[i]] += 1
        for i in range(length):        
            rightSum[nums[i]] -= i
            rightCount[nums[i]] -= 1
            res[i] = (leftCount[nums[i]] - rightCount[nums[i]]) * i - (leftSum[nums[i]]) + rightSum[nums[i]]
            leftSum[nums[i]] += i
            leftCount[nums[i]] += 1
        return res
699