Intervals between identical elements

Array Hash Table Prefix Sum

45.5% acceptance

Feb 25, 2026

955

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_distances(arr: Vec<i32>) -> Vec<i64> {
    use std::collections::HashMap;
    let n = arr.len();
    let mut result = vec![0i64; n];

    // Group indices by value
    let mut groups: HashMap<i32, Vec<usize>> = HashMap::new();
    for (i, &v) in arr.iter().enumerate() {
      groups.entry(v).or_default().push(i);
    }

    for group in groups.values() {
      let k = group.len();
      let total_sum: i64 = group.iter().map(|&x| x as i64).sum();
      let mut left_sum: i64 = 0;
      for (j, &idx) in group.iter().enumerate() {
        let right_sum = total_sum - left_sum - idx as i64;
        // sum |idx - group[m]| = j*idx - left_sum + right_sum - (k-1-j)*idx
        result[idx] = (j as i64 * idx as i64 - left_sum)
          + (right_sum - (k - 1 - j) as i64 * idx as i64);
        left_sum += idx as i64;
      }
    }
    result
  }
}