<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>

# Naive approach
# class Solution:
#     def distance(self, nums: List[int]) -> List[int]:
#         # Initialize the result array
#         arr = [0] * len(nums)
        
#         # Iterate over each element
#         for i in range(len(nums)):
#             # Temporary sum to calculate distances
#             temp_sum = 0
#             found_duplicate = False
            
#             # Check for other occurrences of nums[i]
#             for j in range(len(nums)):
#                 if i != j and nums[i] == nums[j]:
#                     temp_sum += abs(i - j)
#                     found_duplicate = True

#             # If a duplicate was found, update arr[i] with the total distance sum
#             if found_duplicate:
#                 arr[i] = temp_sum
#             else:
#                 arr[i] = 0

#         return arr
'''
Explanation 
Initialization: A result array arr is initialized with zeroes to hold the output values.
Outer Loop: Iterates through each index i of nums.
Inner Loop: Checks all other indices j to find duplicates of nums[i]. If a duplicate is found, it adds the absolute distance |i - j| to temp_sum.
Update arr[i]: After the inner loop, if a duplicate is found (found_duplicate is True), arr[i] is updated with the calculated sum; otherwise, it is set to 0.
Return arr: Finally, return the computed array.
'''      


class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        # Dictionary to store all the indices for each number
        d = defaultdict(list)
        for i, num in enumerate(nums):
            d[num].append(i)

        # Compute the result for each unique number
        for num in d:
            # Calculate prefix sum and other required variables
            pref, sm, n = list(accumulate(d[num])), sum(d[num]), len(d[num])

            # Calculate the distance for each occurrence
            for idx, i in enumerate(d[num]):
                nums[i] = sm + (2 * idx + 2 - n) * i - 2 * pref[idx]

        return nums
42431