Sum of absolute differences in a sorted array

Array Math Prefix Sum

68.2% acceptance

Feb 25, 2026

2199

You are given an integer array nums sorted in non-decreasing order. Build and return an integer array result where result[i] is the summation of absolute differences between nums[i] and all other elements.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_sum_absolute_differences(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let total: i64 = nums.iter().map(|&x| x as i64).sum();
    let mut cum: i64 = 0;
    let mut result = Vec::with_capacity(n);
    for (i, &x) in nums.iter().enumerate() {
      // s_l = sum of nums[0..i-1] = cum (before adding x)
      // s_r = total - cum - x
      // result[i] = i*x - s_l + s_r - (n-1-i)*x
      //            = (2*i - (n-1)) * x + s_r - s_l
      //            = (2*i as i64 - n as i64 + 1) * x as i64 + (total - cum - x as i64) - cum
      let val = (2 * i as i64 - n as i64 + 1) * x as i64
        + (total - cum - x as i64)
        - cum;
      result.push(val as i32);
      cum += x as i64;
    }
    result
  }
}