Sum of distances

Array Hash Table Prefix Sum

32.5% acceptance

Feb 25, 2026

833

You are given a 0-indexed integer array nums. There exists an array arr of length nums.length, where arr[i] is the sum of |i - j| over all j such that nums[j] == nums[i] and j != i. If there is no such j, set arr[i] to be 0. Return the array arr.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn distance(nums: Vec<i32>) -> Vec<i64> {
    let n = nums.len();
    let mut groups: std::collections::HashMap<i32, Vec<usize>> = std::collections::HashMap::new();
    for (i, &v) in nums.iter().enumerate() {
      groups.entry(v).or_default().push(i);
    }

    let mut ans = vec![0i64; n];

    for (_, indices) in &groups {
      let m = indices.len();
      // Prefix sum of indices
      let mut prefix = vec![0i64; m + 1];
      for j in 0..m {
        prefix[j + 1] = prefix[j] + indices[j] as i64;
      }
      let total = prefix[m];
      for (k, &idx) in indices.iter().enumerate() {
        let idx = idx as i64;
        // Elements to the left: k elements, their sum = prefix[k]
        // Cost = idx * k - prefix[k]
        // Elements to the right: (m - k - 1) elements, their sum = total - prefix[k+1]
        // Cost = (total - prefix[k+1]) - idx * (m - k - 1)
        let left = idx * k as i64 - prefix[k];
        let right = (total - prefix[k + 1]) - idx * (m - k - 1) as i64;
        ans[indices[k]] = left + right;
      }
    }
    ans
  }
}