2615. Sum of Distances

Problem Overview

For every element, you need the sum of absolute distances to all other positions that hold the same value.

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?