<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]:
        # 1) Optimal (HashMap; Maths): TC = O(n); SC = O(n)
        # The trick is to just calc. the relative change in the distance sum when going from the last index to the current index.
        # Group the indices together using HashMap:
        d = {}
        for i, v in enumerate(nums):
            if v in d.keys():
                d[v].append(i)
            else:
                d[v] = [i]
        # print(d)  
        l = [0] * len(nums) 
        # print(l)
        for indices in d.values():  
            # Calc. the distance sum using loop (i.e. O(n)) for first index:
            n = len(indices)
            dist_sum = sum(abs(indices[0]-indices[i]) for i in range(1, n))  
            l[indices[0]] = dist_sum
            # print("indices size is",n)  
            # print("first index in indices is", indices[0], "and sum is ",  dist_sum)
            # print(l)
            # Then calc. using maths (multiplication) (i.e. O(1)) for other indices:
            for i in range(1, n):
                dist_moved = indices[i] - indices[i-1]  # from previous index to current one
                # print("moved distance", dist_moved, "to index", i)
                dist_sum -= dist_moved * (n-i)  # distance decrease for n-i elements
                # print("sum decreased for", n,"-",i,"=",n-i, "elements to",n-i,"*",dist_moved,"=", dist_sum)
                dist_sum += dist_moved * i  # distance increase for i elements
                # print("sum increased for i =", i, "elements to", i,"*",dist_moved,"=", dist_sum)
                l[indices[i]] = dist_sum 
                # print(l)
        return l
        
    def distance(self, nums: List[int]) -> List[int]:
        if len(nums) == len(set(nums)):
            return [0] * len(nums) 
        res, d = [0] * len(nums), {}
        for i, val in enumerate(nums):
            if val not in d:
                d[val] = []
            d[val].append(i) 
        for val in d.values():
            prefix_sum = 0
            suffix_sum = sum(val) 
            p = 0
            s = len(val) 
            for i in val:
                prefix_sum += i
                p += 1
                suffix_sum -= i
                s -= 1
                res[i] = -prefix_sum + p*i - s*i + suffix_sum
        return res

    def distance(self, nums: List[int]) -> List[int]:
        num_indices = dict()
        occ = dict()
        for i, num in enumerate(nums):
            if num not in num_indices:
                num_indices[num] = i
                occ[num] = 1
            else:
                num_indices[num] = num_indices[num] + i
                occ[num] = occ[num] + 1
        arr = [0] * len(nums)
        for i in range(len(nums)):
            arr[i] = num_indices[nums[i]] - occ[nums[i]]*i     
            num_indices[nums[i]] = num_indices[nums[i]] - 2*i
            occ[nums[i]] = occ[nums[i]] - 2
        return arr
        
41343