Intervals Between Identical Elements
You are given a 0-indexed array of n integers arr.
The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.
Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].
Note: |x| is the absolute value of x.
Note: This question is the same as 2615: Sum of Distances.
Example 1
Input
arr = [2,1,3,1,2,3,3]Output
[4,2,7,2,4,4,5]For each index, sum the absolute differences to all other indices containing the same value, producing [4, 2, 7, 2, 4, 4, 5].
Example 2
Input
arr = [10,5,10,10]Output
[5,0,3,4]The value 10 appears at indices 0, 2, and 3 while 5 appears only once, so the sums are [5, 0, 3, 4].
Constraints
- n == arr.length
- 1 <= n <= 10^5
- 1 <= arr[i] <= 10^5