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.
In this approach, we will use a dictionary to group indices by the same value they have in the nums array. For each group of indices, we will compute the total distance for each index.
The code starts by creating a dictionary to collect all indices for each unique number in nums. Then for each collected list of indices, it computes pairwise distances using a prefix sum and a suffix sum (remaining total sum).
Time Complexity: O(n), where n is the length of nums. We process each element a constant number of times.
Space Complexity: O(n), for storing the indices in the dictionary.
This approach utilizes prefix and suffix sums to calculate distances. For each unique number's index list, we process two passes: first to calculate distances left-to-right, and second right-to-left, using sums accumulated so far.
This optimized version uses left-to-right and right-to-left passes with accumulated indices' sums for greater performance. Distances are computed in O(1) per index after precomputing necessary sums.
Python
JavaScript
C++
Java
C#
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Approach 1: Dictionary for Index Grouping | Time Complexity: O(n), where n is the length of |
| Approach 2: Prefix and Suffix Sum Calculation | Time Complexity: O(n) |
| Default Approach | — |
| 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. |
Leetcode 2615. Sum of Distances | Weekly Contest 340 | OffCampus Phodenge | Leetcode weekly contest • OffCampus Phodenge | Aman Chowdhury • 2,678 views views
Watch 9 more video solutions →Practice Sum of Distances with our built-in code editor and test cases.
Practice on FleetCode