2615. Sum of Distances

Intuition

For every element, you need the sum of absolute distances to all other positions that hold the same value. The brute-force recomputes this sum from scratch for each element — O(N²) overall. The key insight is that once you sort (or group) the indices sharing a value, you can sweep left-to-right and update a single running total in O(1) per step. When you advance from one index to the next, each of the already-processed left indices moves one step farther, while each of the not-yet-processed right indices moves one step closer — so you just add/subtract multiples of the gap.

Algorithm

1Build a Dictionary mapping each unique value to the sorted list of indices where it appears.
2For each group of indices [idx0, idx1, ..., idx_{n-1}]: initialise `sumSoFar` = sum of all indices in the group and `prevIndex` = 0.
3Iterate i from 0 to n-1. Compute `gap = indices[i] - prevIndex`.
4 Update: `sumSoFar += (i - 1) * gap` (left-side indices each grew gap farther from new position).
5 Update: `sumSoFar -= (n - 1 - i) * gap` (right-side indices each grew gap closer to new position).
6 Set `ans[indices[i]] = sumSoFar`. Set `prevIndex = indices[i]`.
7Return `ans`.

Example Walkthrough

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

1.Group indices: {1: [0,2,3], 3: [1], 2: [4]}.
2.Group for value 1, n=3. sumSoFar = 0+2+3 = 5, prevIndex = 0.
3.i=0, idx=0: gap=0. sumSoFar += (-1)*0 - 2*0 = 5. ans[0]=5. prevIndex=0.
4.i=1, idx=2: gap=2. sumSoFar += 0*2 - 1*2 = 5-2 = 3. ans[2]=3. prevIndex=2.
5.i=2, idx=3: gap=1. sumSoFar += 1*1 - 0*1 = 3+1 = 4. ans[3]=4. prevIndex=3.
6.Groups for 3 and 2 have only one element each, skip. ans[1]=0, ans[4]=0.

Output: [5, 0, 3, 4, 0]

Common Pitfalls

•Use `long` (not `int`) for `sumSoFar` and the final answer — index products can overflow 32-bit integers.
•Groups of size 1 contribute 0 — skip them to avoid unnecessary work.
•The initial `prevIndex = 0` is intentional: the formula self-corrects for the first iteration because i=0 makes the (i-1) term negative, which subtracts the inflated contribution of index 0 from the starting sum.

2615.cs

// Approach: For each element, we need the sum of distances to all other positions with the same value.
// A naive O(N^2) approach re-sums for every element. Instead, group indices by value using a Dictionary,
// then process each group with a single left-to-right sweep using a running prefix-sum adjustment.
// Start with sumSoFar = sum of all indices in the group. For each index at position i in the group:
//   - The i elements to its left each move 'gap' farther away  => sumSoFar += (i-1) * gap
//   - The (n-1-i) elements to its right each move 'gap' closer => sumSoFar -= (n-1-i) * gap
// This gives the exact distance sum for each element in O(group_size) rather than O(group_size^2).
//
// Time: O(N) — each index is processed exactly once across all groups.
// Space: O(N) — for the Dictionary mapping values to their index lists.

public class Solution
{
    public long[] Distance(int[] nums)
    {
        long[] ans = new long[nums.Length];
        var numToIndices = new Dictionary<int, List<int>>();

        for (int i = 0; i < nums.Length; ++i)
        {
            if (!numToIndices.ContainsKey(nums[i]))
                numToIndices[nums[i]] = new List<int>();

            numToIndices[nums[i]].Add(i);
        }

        foreach (var indices in numToIndices.Values)
        {
            int n = indices.Count;
            if (n == 1)
                continue;

            long sumSoFar = indices.Sum(i => (long)i);
            int prevIndex = 0;
            for (int i = 0; i < n; ++i)
            {
                sumSoFar += (i - 1L) * (indices[i] - prevIndex);
                sumSoFar -= (n - 1 - i) * (indices[i] - prevIndex);
                ans[indices[i]] = sumSoFar;
                prevIndex = indices[i];
            }
        }

        return ans;
    }
}

Was this solution helpful?