<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]:
        cache = defaultdict(list)
        memo_index = {}
        for i, num in enumerate(nums):
            if not num in cache:
                cache[num].append((0,i))
                memo_index[i] = 0
            else:
                n = len(cache[num])
                prev_index, prev_prefixSum = cache[num][n-1]
                cache[num].append((prev_index + 1,i + prev_prefixSum))
                memo_index[i] = prev_index + 1
        
        print(cache)

        def helper(i,num):
            index_in_cache = memo_index[i]
            n = len(cache[num])
            leftSum = 0
            rightSum = 0
            if index_in_cache == 0:
                leftSum = 0
            else:
                number_index_left = index_in_cache
                leftSum = i * index_in_cache - cache[num][index_in_cache-1][1]
            
            if index_in_cache == n-1:
                rightSum = 0
            else:
                number_index_right = n - 1 - (index_in_cache + 1) + 1
                rightSum = cache[num][n-1][1] - cache[num][index_in_cache][1] - i * number_index_right
            return leftSum + rightSum

        n = len(nums)
        res = [0] * n
        for i in range(n):
            if len(cache[nums[i]]) == 1:
                res[i] = 0
            else:
                res[i] = helper(i,nums[i])
        
        return res
67081