Intervals Between Identical Elements

Problem

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] isthe sum of intervals between arr[i]and each element inarr with the same value asarr[i].

Note: |x| is the absolute value of x.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7


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

Note: This question is the same as 2615: Sum of Distances.

Solution

Method 1 – Prefix Sum Grouping

Intuition

For each value, we want to efficiently compute the sum of distances between all indices where it occurs. By grouping indices for each value and using prefix sums, we can compute the answer for each index in linear time per group.

Approach

Use a hash map to collect all indices for each unique value in arr.
For each group of indices:
- Compute prefix sums of the indices.
- For each index, calculate the sum of distances to all other indices using prefix sums.
Fill the answer array accordingly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


vector<long long> getDistances(vector<int>& arr) {
    unordered_map<int, vector<int>> pos;
    int n = arr.size();
    for (int i = 0; i < n; ++i) pos[arr[i]].push_back(i);
    vector<long long> ans(n);
    for (auto& [_, idxs] : pos) {
        int m = idxs.size();
        vector<long long> pre(m+1);
        for (int i = 0; i < m; ++i) pre[i+1] = pre[i] + idxs[i];
        for (int i = 0; i < m; ++i) {
            long long left = (long long)i * idxs[i] - pre[i];
            long long right = (pre[m] - pre[i+1]) - (long long)(m-i-1) * idxs[i];
            ans[idxs[i]] = left + right;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func getDistances(arr []int) []int64 {
    pos := map[int][]int{}
    n := len(arr)
    for i, v := range arr {
        pos[v] = append(pos[v], i)
    }
    ans := make([]int64, n)
    for _, idxs := range pos {
        m := len(idxs)
        pre := make([]int64, m+1)
        for i := 0; i < m; i++ {
            pre[i+1] = pre[i] + int64(idxs[i])
        }
        for i := 0; i < m; i++ {
            left := int64(i)*int64(idxs[i]) - pre[i]
            right := pre[m] - pre[i+1] - int64(m-i-1)*int64(idxs[i])
            ans[idxs[i]] = left + right
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public long[] getDistances(int[] arr) {
        Map<Integer, List<Integer>> pos = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; ++i) pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        long[] ans = new long[n];
        for (var idxs : pos.values()) {
            int m = idxs.size();
            long[] pre = new long[m+1];
            for (int i = 0; i < m; ++i) pre[i+1] = pre[i] + idxs.get(i);
            for (int i = 0; i < m; ++i) {
                long left = (long)i * idxs.get(i) - pre[i];
                long right = (pre[m] - pre[i+1]) - (long)(m-i-1) * idxs.get(i);
                ans[idxs.get(i)] = left + right;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    fun getDistances(arr: IntArray): LongArray {
        val pos = mutableMapOf<Int, MutableList<Int>>()
        for (i in arr.indices) pos.getOrPut(arr[i]) { mutableListOf() }.add(i)
        val ans = LongArray(arr.size)
        for (idxs in pos.values) {
            val m = idxs.size
            val pre = LongArray(m+1)
            for (i in 0 until m) pre[i+1] = pre[i] + idxs[i]
            for (i in 0 until m) {
                val left = i.toLong() * idxs[i] - pre[i]
                val right = pre[m] - pre[i+1] - (m-i-1).toLong() * idxs[i]
                ans[idxs[i]] = left + right
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


def get_distances(arr: list[int]) -> list[int]:
    from collections import defaultdict
    pos = defaultdict(list)
    for i, v in enumerate(arr):
        pos[v].append(i)
    ans = [0] * len(arr)
    for idxs in pos.values():
        m = len(idxs)
        pre = [0] * (m+1)
        for i in range(m):
            pre[i+1] = pre[i] + idxs[i]
        for i in range(m):
            left = i * idxs[i] - pre[i]
            right = pre[m] - pre[i+1] - (m-i-1) * idxs[i]
            ans[idxs[i]] = left + right
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


use std::collections::HashMap;
fn get_distances(arr: Vec<i32>) -> Vec<i64> {
    let mut pos: HashMap<i32, Vec<usize>> = HashMap::new();
    for (i, &v) in arr.iter().enumerate() {
        pos.entry(v).or_default().push(i);
    }
    let n = arr.len();
    let mut ans = vec![0i64; n];
    for idxs in pos.values() {
        let m = idxs.len();
        let mut pre = vec![0i64; m+1];
        for i in 0..m {
            pre[i+1] = pre[i] + idxs[i] as i64;
        }
        for i in 0..m {
            let left = i as i64 * idxs[i] as i64 - pre[i];
            let right = pre[m] - pre[i+1] - (m-i-1) as i64 * idxs[i] as i64;
            ans[idxs[i]] = left + right;
        }
    }
    ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


function getDistances(arr: number[]): number[] {
  const pos: Record<number, number[]> = {};
  for (let i = 0; i < arr.length; ++i) {
    if (!pos[arr[i]]) pos[arr[i]] = [];
    pos[arr[i]].push(i);
  }
  const ans = Array(arr.length).fill(0);
  for (const idxs of Object.values(pos)) {
    const m = idxs.length;
    const pre = Array(m+1).fill(0);
    for (let i = 0; i < m; ++i) pre[i+1] = pre[i] + idxs[i];
    for (let i = 0; i < m; ++i) {
      const left = i * idxs[i] - pre[i];
      const right = pre[m] - pre[i+1] - (m-i-1) * idxs[i];
      ans[idxs[i]] = left + right;
    }
  }
  return ans;
}

Complexity

⏰ Time complexity: O(n) — Each index is processed a constant number of times.
🧺 Space complexity: O(n) — For storing positions and prefix sums.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Prefix Sum Grouping#

Intuition#

Approach#

Code#

Complexity#