<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
'''
Explanation of Your Code
Dictionary to Store Indices (d):

You are using a defaultdict of lists to store all the indices for each unique number in the input array nums.
This allows you to quickly access all indices where each number appears.
Prefix Sum Calculation (pref):

For each number in the dictionary, you calculate the prefix sum (pref) using the accumulate function from the itertools module.
This prefix sum helps in calculating the sum of distances efficiently.
Compute Distance Using Hint #3:

For each index i where the current number appears, you compute the required distance using the formula:
python
Copy code
nums[i] = sm + (2 * idx + 2 - n) * i - 2 * pref[idx]
This formula leverages prefix sums (pref) and properties of arithmetic series to compute the total distance efficiently.
Why Your Code Works
The logic is based on efficiently computing the sum of absolute differences using prefix sums to reduce redundant calculations.
The time complexity of your solution is O(n), which is optimal for the problem constraints.
'''
45331