Sum of Distances

Sum of Distances

What is this problem about?

The "Sum of Distances" problem asks you to calculate a value for each element in an array based on other elements with the same value. For a given index i, you need to find all other indices j such that nums[i] == nums[j]. The value for index i is the sum of the absolute differences |i - j| for all such j. You must return an array of these sums.

Why is this asked in interviews?

Google and BNY Mellon ask this to test optimization skills. A brute-force approach (searching the whole array for each element) would be O(N²), which is unusable for large datasets. The problem requires the use of Hash Maps for grouping indices and Prefix Sums to calculate distances in linear time. It evaluates a candidate's ability to simplify mathematical summations.

Algorithmic pattern used

The pattern is "Grouping with Prefix Sums."

1. Use a Hash Map to store a list of all indices for each unique value in the array.
2. For each list of indices [p1, p2, p3...pn], you need to calculate the sum of distances for each pi.
3. This is identical to the "Sum of Absolute Differences in a Sorted Array" logic. For an index pi, the sum of distances to indices on its left is (pi * count_left) - sum_left_indices, and for indices on its right, it's sum_right_indices - (pi * count_right).

Example explanation

Array: [1, 3, 1, 1, 2]

• For the value '1', the indices are [0, 2, 3].
• For index 0: Distances are |0-2| + |0-3| = 2 + 3 = 5.
• For index 2: Distances are |2-0| + |2-3| = 2 + 1 = 3.
• For index 3: Distances are |3-0| + |3-2| = 3 + 1 = 4. The result array would have these values at indices 0, 2, and 3.

Common mistakes candidates make

1. O(N²) Complexity: Trying to use nested loops to find matching values and calculate distances.
2. Memory Overhead: Storing too much redundant information in the hash map.
3. Mathematical errors: Getting the prefix sum formula wrong, leading to incorrect distance calculations.

Interview preparation tip

Master the "Contribution of distances" formula. It allows you to calculate the sum of distances from one point to a set of other points in O(1) time if you know the prefix sums of those points. This is a very powerful trick in geometry and array problems.