Watch 10 video solutions for Sum of Distances, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by OffCampus Phodenge | Aman Chowdhury has 2,678 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums. There exists an array arr of length nums.length, where arr[i] is the sum of |i - j| over all j such that nums[j] == nums[i] and j != i. If there is no such j, set arr[i] to be 0.
Return the array arr.
Example 1:
Input: nums = [1,3,1,1,2] Output: [5,0,3,4,0] Explanation: When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5. When i = 1, arr[1] = 0 because there is no other index with value 3. When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3. When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4. When i = 4, arr[4] = 0 because there is no other index with value 2.
Example 2:
Input: nums = [0,5,3] Output: [0,0,0] Explanation: Since each element in nums is distinct, arr[i] = 0 for all i.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
Note: This question is the same as 2121: Intervals Between Identical Elements.
Problem Overview: You are given an integer array nums. For each index i, compute the sum of absolute differences between i and every other index j where nums[i] == nums[j]. The result is an array where each position stores the total distance to all indices containing the same value.
The core observation: indices with the same value form independent groups. Instead of comparing every pair in the entire array, you only care about distances within each value group.
Approach 1: Dictionary for Index Grouping (O(n2) time, O(n) space)
Group indices by value using a hash map. Iterate through nums and store each index in a list mapped to its value. For every group, compute the distance for each index by iterating through the entire list of indices and summing |i - j|. This approach is straightforward because the problem reduces to pairwise distance calculations within each group. However, if a value appears k times, computing distances costs O(k^2). In the worst case where all elements are identical, the complexity becomes O(n^2). The space complexity remains O(n) due to the grouping structure. This approach demonstrates the grouping insight using a hash table, but it does not scale well for large inputs.
Approach 2: Prefix and Suffix Sum Calculation (O(n) time, O(n) space)
The optimized solution still groups indices by value, but computes distances using prefix sums instead of pairwise comparisons. Suppose a value appears at indices [i0, i1, i2, ...]. When processing index ik, distances to the left are calculated using the number of previous indices and their cumulative sum. Distances to the right are computed similarly with remaining indices. Maintaining running prefix sums allows you to calculate the total distance in constant time per index. Each index participates in exactly one pass within its group, producing an overall time complexity of O(n) and space complexity of O(n). This technique combines array traversal with prefix sum aggregation to eliminate redundant distance calculations.
Recommended for interviews: Interviewers typically expect the prefix-sum optimization. The brute grouping approach shows you understand how to isolate equal values using a hash map. The prefix/suffix computation demonstrates algorithmic maturity by reducing repeated work and achieving linear time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dictionary for Index Grouping | O(n²) worst case | O(n) | Useful for understanding the problem and validating the grouping insight. |
| Prefix and Suffix Sum Calculation | O(n) | O(n) | Preferred solution for interviews and production due to linear performance. |