385. Sum of Distances

For each index i, walk every other index j; if nums[j] == nums[i], add |i - j| to arr[i].

Approach

1. Initialise arr with zeros.
2. For each i, scan every j != i and accumulate |i - j| whenever the values match.

Complexity

• Time: O(n²) — quadratic; too slow for n = 10^5.
• Space: O(n) — the answer array.

import java.util.*;

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && nums[i] == nums[j]) {
                    arr[i] += Math.abs(i - j);
                }
            }
        }
        return arr;
    }
}

Indices with different values don't talk to each other. So we can solve each value-group independently. Within a group, the absolute-distance sum at position p simplifies into (things on the left) + (things on the right), both expressible with prefix sums. Each arr[i] then takes constant time.

Splitting by value

arr[i] is the sum over indices j where nums[j] == nums[i]. So elements with different values contribute nothing — we can group indices by value first.

For nums = [1, 3, 1, 1, 2], the groups are:

Singleton groups contribute 0 to every arr[i] in them. The interesting group is [0, 2, 3].

Removing absolute value with order

Inside a group, the indices are already in increasing order: i₀ < i₁ < … < i_{k-1}. For the element at position p in that list with index iₚ:

• For q < p: i_q < iₚ, so |i_q - iₚ| = iₚ - i_q.
• For q > p: i_q > iₚ, so |i_q - iₚ| = i_q - iₚ.

Sum of distances at index iₚ is therefore:

(iₚ - i₀) + (iₚ - i₁) + ... + (iₚ - i_{p-1})       ← from the left
+ (i_{p+1} - iₚ) + ... + (i_{k-1} - iₚ)             ← from the right

Group the constants on each side:

left  = p · iₚ - (i₀ + i₁ + ... + i_{p-1})
right = (i_{p+1} + ... + i_{k-1}) - (k - 1 - p) · iₚ

Both pieces are computable in O(1) if we keep a running prefix sum and the group's total sum.

Steps

1. Group indices by value (one pass): groups[v].append(i).
2. Initialise arr = [0] * n.
3. For each group:
   • Let total = sum(group) and k = len(group).
   • Let prefix = 0 (running sum of indices seen so far in the group).
   • For position p, idx = group[p]:
     • left = p · idx - prefix
     • right = (total - prefix - idx) - (k - 1 - p) · idx
     • arr[idx] = left + right
     • prefix += idx

Walk-through

nums = [1, 3, 1, 1, 2]. Process the group [0, 2, 3] for value 1:

total = 0 + 2 + 3 = 5, k = 3.

(Actually the prefix update is after the computation: prefix starts at 0 for p=0, becomes 0 after, then 0+2=2 for p=2, then 2+3=5 for p=3.)

For the singletons ([1] and [4]), k = 1, so p = 0, prefix = 0, total = idx, both left and right are 0. So arr[1] = 0, arr[4] = 0.

Final: arr = [5, 0, 3, 4, 0]. ✓

Edge cases

• All distinct values: every group is a singleton; the answer is all zeros.
• All identical values: one big group; the formulas still hold.

Complexity

• Time: O(n) — each index is touched once when grouping and once when computing.
• Space: O(n) — the groups and the output.