Skip to main content
Talentd

Sum of Distances - Solution & Explanation

MediumArrayHash TablePrefix Sum12 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 <= 105
  • 0 <= nums[i] <= 109

 

Note: This question is the same as 2121: Intervals Between Identical Elements.

Approach Overview

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 1: Approach 1: Dictionary for Index Grouping

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).

Code

PythonC++JavaC

Python

C++

Java

C

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Prefix and Suffix Sum Calculation

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.

Code

PythonJavaScriptC++JavaC#

Python

JavaScript

C++

Java

C#

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Dictionary for Index Grouping

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.

Approach 2: Prefix and Suffix Sum Calculation

Time Complexity: O(n)
Space Complexity: O(n)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dictionary for Index GroupingO(n²) worst caseO(n)Useful for understanding the problem and validating the grouping insight.
Prefix and Suffix Sum CalculationO(n)O(n)Preferred solution for interviews and production due to linear performance.

Video Solution

Sum of Distances | Detailed | From Brute Force | Dry Runs | Leetcode 2615 | codestorywithMIK • codestorywithMIK • 9,639 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Distances easy or hard?
Sum of Distances is considered a Medium difficulty problem. The challenge lies in recognizing that repeated pairwise distance calculations can be replaced with prefix sum math to achieve an O(n) solution.
Sum of Distances Python/Java solution
Most implementations follow the same logic across languages: group indices using a dictionary or map, then compute prefix and suffix distance contributions. Python uses defaultdict or dict lists, while Java typically uses HashMap<Integer, List<Integer>> with prefix sum calculations.
How to solve Sum of Distances in O(n)?
First group indices by value using a hash map. For each group, maintain running prefix sums of indices. While iterating through the group, compute distances to the left using the count and sum of previous indices, and distances to the right using remaining indices. This allows constant-time distance computation per index.
What is the best approach for Sum of Distances?
The best approach uses a hash map to group indices with the same value and then applies prefix and suffix sums to compute distances efficiently. Each index’s contribution is calculated using cumulative sums of previous and remaining indices. This reduces the total complexity to O(n) time and O(n) space.
Is Sum of Distances asked at Google/Amazon/Meta?
Sum of Distances reflects patterns frequently used in interviews at companies like Google, Amazon, and Meta. The problem tests hash map grouping and prefix sum optimization, both common techniques in array processing interview questions.
What data structure is used in Sum of Distances?
The solution primarily uses a hash table (dictionary) to group indices by value. Arrays store the final results, and prefix sums help compute distance contributions efficiently. These structures allow constant-time lookups and linear-time traversal.
What is the time complexity of Sum of Distances?
The optimal solution runs in O(n) time because each array index is processed once within its value group. A naive pairwise comparison inside groups leads to O(n^2) time in the worst case. The prefix sum optimization eliminates repeated distance calculations.

Ready to solve this problem?

Practice Sum of Distances with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All Duplicates in an Array

Next

Minimum Operations to Make All Array Elements Equal