problemmediumalgorithmsleetcode-2615leetcode 2615leetcode2615

Sum of Distances

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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 arrayarr .

Examples

Example 1

Input: nums = [1,3,1,1,2]
Output: [5,0,3,4,0]
Explanation: 
When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5. 
When i = 1, arr[1] = 0 because there is no other index with value 3.
When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3. 
When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4. 
When i = 4, arr[4] = 0 because there is no other index with value 2.

Example 2

Input: nums = [0,5,3]
Output: [0,0,0]
Explanation: Since each element in nums is distinct, arr[i] = 0 for all i.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

Note: This question is the same as [ 2121: Intervals Between Identical Elements.](https://leetcode.com/problems/intervals-between-identical- elements/description/)

Solution

Method 1 – Prefix Sums by Value Groups

Intuition

For each value, collect all its indices. For each index, the sum of distances to all other indices with the same value can be computed efficiently using prefix sums. This avoids brute-force and leverages the sorted order of indices.

Approach

  1. Use a hash map to group indices by value.
  2. For each group of indices:
    • Compute prefix sums of indices.
    • For each index, calculate the sum of distances to all other indices using prefix sums (left and right contributions).
  3. Fill the answer array accordingly.
  4. Return the answer array.

Code

C++
class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < n; ++i) pos[nums[i]].push_back(i);
        vector<long long> ans(n);
        for (auto& [val, 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 = 1LL * idxs[i] * i - pre[i];
                long long right = (pre[m] - pre[i+1]) - 1LL * idxs[i] * (m - i - 1);
                ans[idxs[i]] = left + right;
            }
        }
        return ans;
    }
};
Go
func distance(nums []int) []int64 {
    n := len(nums)
    pos := map[int][]int{}
    for i, v := range nums {
        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(idxs[i])*int64(i) - pre[i]
            right := (pre[m] - pre[i+1]) - int64(idxs[i])*int64(m-i-1)
            ans[idxs[i]] = left + right
        }
    }
    return ans
}
Java
class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) pos.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        long[] ans = new long[n];
        for (List<Integer> 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)idxs.get(i) * i - pre[i];
                long right = (pre[m] - pre[i+1]) - (long)idxs.get(i) * (m - i - 1);
                ans[idxs.get(i)] = left + right;
            }
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun distance(nums: IntArray): LongArray {
        val n = nums.size
        val pos = mutableMapOf<Int, MutableList<Int>>()
        for (i in nums.indices) pos.getOrPut(nums[i]) { mutableListOf() }.add(i)
        val ans = LongArray(n)
        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 = idxs[i].toLong() * i - pre[i]
                val right = (pre[m] - pre[i+1]) - idxs[i].toLong() * (m - i - 1)
                ans[idxs[i]] = left + right
            }
        }
        return ans
    }
}
Python
class Solution:
    def distance(self, nums: list[int]) -> list[int]:
        from collections import defaultdict
        n = len(nums)
        pos = defaultdict(list)
        for i, v in enumerate(nums):
            pos[v].append(i)
        ans = [0] * n
        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 = idxs[i] * i - pre[i]
                right = (pre[m] - pre[i+1]) - idxs[i] * (m - i - 1)
                ans[idxs[i]] = left + right
        return ans
Rust
impl Solution {
    pub fn distance(nums: Vec<i32>) -> Vec<i64> {
        use std::collections::HashMap;
        let n = nums.len();
        let mut pos: HashMap<i32, Vec<usize>> = HashMap::new();
        for (i, &v) in nums.iter().enumerate() {
            pos.entry(v).or_default().push(i);
        }
        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 = idxs[i] as i64 * i as i64 - pre[i];
                let right = (pre[m] - pre[i+1]) - idxs[i] as i64 * (m as i64 - i as i64 - 1);
                ans[idxs[i]] = left + right;
            }
        }
        ans
    }
}
TypeScript
class Solution {
    distance(nums: number[]): number[] {
        const n = nums.length;
        const pos: Record<number, number[]> = {};
        for (let i = 0; i < n; i++) {
            if (!pos[nums[i]]) pos[nums[i]] = [];
            pos[nums[i]].push(i);
        }
        const ans = new Array(n).fill(0);
        for (const idxs of Object.values(pos)) {
            const m = idxs.length;
            const pre = new 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 = idxs[i] * i - pre[i];
                const right = (pre[m] - pre[i+1]) - idxs[i] * (m - i - 1);
                ans[idxs[i]] = left + right;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each index is processed a constant number of times, and prefix sums are linear in total.
  • 🧺 Space complexity: O(n) — For storing positions and prefix sums for each value.

Comments