Formatted question description: https://leetcode.ca/all/2121.html

# 2121. Intervals Between Identical Elements (Medium)

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`

.

**Example 1:**

Input:arr = [2,1,3,1,2,3,3]Output:[4,2,7,2,4,4,5]Explanation:- Index 0: Another 2 is found at index 4. |0 - 4| = 4 - Index 1: Another 1 is found at index 3. |1 - 3| = 2 - Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7 - Index 3: Another 1 is found at index 1. |3 - 1| = 2 - Index 4: Another 2 is found at index 0. |4 - 0| = 4 - Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4 - Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

**Example 2:**

Input:arr = [10,5,10,10]Output:[5,0,3,4]Explanation:- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5 - Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0. - Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3 - Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

**Constraints:**

`n == arr.length`

`1 <= n <= 10`

^{5}`1 <= arr[i] <= 10`

^{5}

**Related Topics**:

Array, Hash Table, Prefix Sum

**Similar Questions**:

## Solution 1.

Assume number `k`

appears at indices `1, 3, 5, 7`

.

For index `1`

, `ans[1] = |3-1|+|5-1|+|7-1| = (3+5+7) - 3*1`

.

For index `3`

, `ans[3] = |3-1|+|5-3|+|7-3| = (5+7) - 2*3 + 1*3 - 1`

…

We can find the following pattern:

Here only consider the indices of the same numbers. Let `rightSum`

/`leftSum`

be the sum of indices to the right/left of `i`

, and `rightCnt`

/`leftCnt`

be the number of indices to the right/left of `i`

.

```
ans[i] = rightSum - rightCnt * i + leftCnt * i - leftSum
```

```
// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<long long> getDistances(vector<int>& A) {
unordered_map<int, long> leftSum, leftCnt, rightSum, rightCnt;
int N = A.size();
for (int i = 0; i < N; ++i) {
rightSum[A[i]] += i;
++rightCnt[A[i]];
}
vector<long long> ans(N);
for (int i = 0; i < N; ++i) {
rightSum[A[i]] -= i;
rightCnt[A[i]]--;
ans[i] = rightSum[A[i]] - rightCnt[A[i]] * i + leftCnt[A[i]] * i - leftSum[A[i]];
leftSum[A[i]] += i;
leftCnt[A[i]]++;
}
return ans;
}
};
```

We can update the formula to the following

```
ans[i] = (rightSum - leftSum) - (rightCnt - leftCnt) * i
= diffSum - diffCnt * i
```

In this way, we only need to keep track of the diffs.

```
// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<long long> getDistances(vector<int>& A) {
unordered_map<int, long> diffSum, diffCnt;
int N = A.size();
for (int i = 0; i < N; ++i) {
diffSum[A[i]] += i;
++diffCnt[A[i]];
}
vector<long long> ans(N);
for (int i = 0; i < N; ++i) {
diffSum[A[i]] -= i;
diffCnt[A[i]]--;
ans[i] = diffSum[A[i]] - diffCnt[A[i]] * i;
diffSum[A[i]] -= i;
diffCnt[A[i]]--;
}
return ans;
}
};
```

Minor simplification: We can include `|i-i| = 0`

in the formula.

For example:

For index `1`

, `ans[1] = |1-1|+|3-1|+|5-1|+|7-1| = (1+3+5+7) - 4*1`

.

For index `3`

, `ans[3] = |3-1|+|3-3|+|5-3|+|7-3| = (3+5+7) - 3*3 + 1*3 - 1`

…

Now we can define `rightSum`

and `rightCnt`

be the sum/count of indices `>= i`

.

```
// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<long long> getDistances(vector<int>& A) {
long long diffSum[100001] = {}, diffCnt[100001] = {}, N = A.size();
for (int i = 0; i < N; ++i) {
diffSum[A[i]] += i;
diffCnt[A[i]]++;
}
vector<long long> ans(N);
for (int i = 0; i < N; ++i) {
ans[i] = diffSum[A[i]] - diffCnt[A[i]] * i;
diffSum[A[i]] -= 2 * i;
diffCnt[A[i]] -= 2;
}
return ans;
}
};
```

## Solution 2.

Similar to 1685. Sum of Absolute Differences in a Sorted Array (Medium)

```
// OJ: https://leetcode.com/problems/intervals-between-identical-elements/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<long long> getDistances(vector<int>& A) {
unordered_map<int, vector<int>> m;
int N = A.size();
vector<long long> ans(N);
for (int i = 0; i < N; ++i) m[A[i]].push_back(i);
for (auto &[n, v] : m) {
long total = accumulate(begin(v), end(v), 0L), right = total;
for (long i = 0; i < v.size(); ++i) {
ans[v[i]] = right - (v.size() - i) * v[i] + i * v[i] - (total - right);
right -= v[i];
}
}
return ans;
}
};
```