Sum of Distances

What the problem is really asking

For every index i, we only care about other indices that contain the same value as nums[i].

If those matching indices are far away, they add a bigger amount. If there are no other matching indices, the answer for that position is 0.

So the core task is:

for each value, solve all of its indices together

Intuition

Trying every pair of equal values is too slow. In the worst case, all numbers are the same, and then every index would compare with almost every other index.

Instead, group the indices by value.

For example:

nums = [1, 3, 1, 1, 2]

The groups are:

1 -> [0, 2, 3]
3 -> [1]
2 -> [4]

Now each group is already sorted because we collect indices while scanning left to right.

For the group [0, 2, 3], we can compute the answer for every index using prefix sums instead of checking all pairs.

Approach: Grouping + prefix sum

Suppose one group has indices:

a0 < a1 < a2 < ... < a(m - 1)

For a current index ai, every index on the left is smaller, so its contribution is:

(ai - a0) + (ai - a1) + ... + (ai - a(i - 1))

That becomes:

i * ai - prefix

where prefix is the sum of all earlier indices in this group.

Every index on the right is larger, so its contribution is:

(a(i + 1) - ai) + (a(i + 2) - ai) + ... + (a(m - 1) - ai)

If total is the sum of all indices in the group, then the sum of indices to the right is:

total - prefix - ai

There are m - i - 1 indices on the right, so the right contribution is:

(total - prefix - ai) - (m - i - 1) * ai

Add both sides, store the result at the original index, and move the prefix forward.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> groups = new HashMap<>();

        for (int i = 0; i < n; i++) {
            groups.computeIfAbsent(nums[i], key -> new ArrayList<>()).add(i);
        }

        long[] answer = new long[n];

        for (List<Integer> indices : groups.values()) {
            long total = 0;

            for (int index : indices) {
                total += index;
            }

            long prefix = 0;
            int size = indices.size();

            for (int i = 0; i < size; i++) {
                int index = indices.get(i);
                long left = (long) i * index - prefix;
                long right = (total - prefix - index) - (long) (size - i - 1) * index;

                answer[index] = left + right;
                prefix += index;
            }
        }

        return answer;
    }
}

Dry run

Take:

nums = [1, 3, 1, 1, 2]

For value 1, the indices are:

[0, 2, 3]

The total index sum is:

0 + 2 + 3 = 5

Now compute each position in that group.

For index 0:

left = 0
right = (2 - 0) + (3 - 0) = 5
answer[0] = 5

For index 2:

left = 2 - 0 = 2
right = 3 - 2 = 1
answer[2] = 3

For index 3:

left = (3 - 0) + (3 - 2) = 4
right = 0
answer[3] = 4

The values 3 and 2 appear only once, so their answers stay 0.

Final answer:

[5, 0, 3, 4, 0]

Why this works

Inside one value group, the indices are sorted.

That lets us remove the absolute value:

• for indices before ai, |ai - aj| becomes ai - aj
• for indices after ai, |ai - aj| becomes aj - ai

Prefix sums tell us the sum of everything before the current index, and the group total tells us the sum of everything after it.

So every index in a group can be solved in O(1) after we know the group total.

Common mistakes

1. Comparing every equal pair

That becomes O(n^2) when many elements are the same, which is too slow for n = 100000.

2. Forgetting to use long

The answer can be much larger than an int. For example, if many equal values are spread across the array, the sum of distances can cross 2^31 - 1.

3. Sorting the whole input unnecessarily

If we collect indices from left to right, each value's list is already sorted. Languages without a convenient hash-map-of-lists can sort (value, index) pairs, but the main idea does not require sorting the original array.

Complexity Analysis

Let n be the length of nums.

Time Complexity: O(n)

Each index is added to exactly one group, and each grouped index is processed once.

Space Complexity: O(n)

The hash table stores all grouped indices, and the answer array has length n.