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 <= 105
• 1 <= arr[i] <= 105

Companies:
TuSimple, Wayve

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 = |3-1|+|5-1|+|7-1| = (3+5+7) - 3*1.

For index 3, ans = |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|+|3-1|+|5-1|+|7-1| = (1+3+5+7) - 4*1.

For index 3, ans = |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 = {}, diffCnt = {}, 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.

// 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;
}
};