Sum of Distances solution and explanation
Google
9 more videos on this problem
Sum of Distances | Detailed | From Brute Force | Dry Runs | Leetcode 2615 | codestorywithMIKcodestorywithMIK · 32:20 · 9K views
Sum Of Distances - Prefix Sum / HashMap - Leetcode 2615 - PythonCheatCode Ninja · 7:16 · 2K views
6360. Sum of Distances - LEETCODE WEEKLY CONTEST 340 (Logic explained in details)Joyjit Codes · 10:01 · 2K views
2615. Sum of Distances (Leetcode Medium)Programming Live with Larry · 12:45 · 1K views
2615 Sum of Distances, Brute Force to Optimized solutionReduceComplexity · 18:15 · 1K views
leetcode 2615 | Sum of Distances | leetcode POTD| Prefix sum | hash map| dsaCode With Vick · 17:47 · 1K views
Leetcode 2615: Sum of DistancesAlgorithms Casts · 22:32 · 884 views
2615. Sum of Distances | Leetcode Daily - PythonLeetcode Daily · 6:23 · 579 views
Sum of Distances | LeetCode 2615 - Pythonimpoldev · 17:50 · 338 views
2615. Sum of Distances | Medium | Leetcode Weekly Contest 340 | JAVA | Solution.Optimization · 4:00 · 143 views
The problem
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.
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.
def sum_of_distances(nums):
from collections import defaultdict
value_to_indices = defaultdict(list)
for index, value in enumerate(nums):
value_to_indices[value].append(index)
result = [0] * len(nums)
for indices in value_to_indices.values():
total_sum = sum(indices)
n = len(indices)
prefix_sum = 0
for i in range(n):
index = indices[i]
total_sum -= index
result[index] = total_sum - (n - i - 1) * index + i * index - prefix_sum
prefix_sum += index
return resultimport java.util.*;
public class SumOfDistances {
public static int[] sumOfDistances(int[] nums) {
Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
valueToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
}
int[] result = new int[nums.length];
for (List<Integer> indices : valueToIndices.values()) {
int totalSum = indices.stream().mapToInt(Integer::intValue).sum();
int prefixSum = 0;
int m = indices.size();
for (int i = 0; i < m; i++) {
int index = indices.get(i);
totalSum -= index;
result[index] = totalSum - (m - i - 1) * index + i * index - prefixSum;
prefixSum += index;
}
}
return result;
}
}#include <vector>
#include <unordered_map>
#include <numeric>
using namespace std;
vector<int> sumOfDistances(const vector<int>& nums) {
unordered_map<int, vector<int>> value_to_indices;
int n = nums.size();
for (int i = 0; i < n; ++i) {
value_to_indices[nums[i]].emplace_back(i);
}
vector<int> result(n, 0);
for (const auto& pair : value_to_indices) {
const auto& indices = pair.second;
int total_sum = accumulate(indices.begin(), indices.end(), 0);
int prefix_sum = 0;
int m = indices.size();
for (int i = 0; i < m; ++i) {
int idx = indices[i];
total_sum -= idx;
result[idx] = total_sum - (m - i - 1) * idx + i * idx - prefix_sum;
prefix_sum += idx;
}
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int* sumOfDistances(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
int* result = (int*)malloc(numsSize * sizeof(int));
memset(result, 0, numsSize * sizeof(int));
struct Node {
int index;
struct Node* next;
} **hashTable = (struct Node**)calloc(numsSize, sizeof(struct Node*));
for (int i = 0; i < numsSize; ++i) {
int hash = nums[i] % numsSize;
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->index = i;
newNode->next = hashTable[hash];
hashTable[hash] = newNode;
}
for (int i = 0; i < numsSize; ++i) {
int hash = nums[i] % numsSize;
struct Node* current = hashTable[hash];
int prefixSum = 0, suffixSum = 0, count = 0;
while (current) {
suffixSum += current->index;
count++;
current = current->next;
}
current = hashTable[hash];
while (current) {
int idx = current->index;
suffixSum -= idx;
result[idx] += suffixSum - ((count - 1) - prefixSum);
prefixSum += idx;
current = current->next;
}
}
for (int i = 0; i < numsSize; ++i) {
struct Node* current = hashTable[i];
while (current) {
struct Node* temp = current;
current = current->next;
free(temp);
}
}
free(hashTable);
return result;
}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.
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.
def sum_of_distances(nums):
from collections import defaultdict
value_to_indices = defaultdict(list)
result = [0] * len(nums)
for i, num in enumerate(nums):
value_to_indices[num].append(i)
for indices in value_to_indices.values():
n = len(indices)
left_total_sum = [0] * n
left_sum = 0
for i in range(1, n):
left_sum += indices[i - 1]
left_total_sum[i] = left_total_sum[i - 1] + indices[i] - left_sum
right_sum = 0
for i in range(n - 2, -1, -1):
right_sum += indices[i + 1]
result[indices[i]] += right_sum - (n - i - 1) * indices[i]
result[indices[i]] += left_total_sum[i]
return resultimport java.util.*;
public class SumOfDistances {
public static int[] sumOfDistances(int[] nums) {
Map<Integer, ArrayList<Integer>> valueToIndices = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
valueToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
}
int[] result = new int[nums.length];
for (ArrayList<Integer> indices : valueToIndices.values()) {
int n = indices.size();
int[] leftTotalSum = new int[n];
int leftSum = 0;
for (int i = 1; i < n; i++) {
leftSum += indices.get(i - 1);
leftTotalSum[i] = leftTotalSum[i - 1] + indices.get(i) - leftSum;
}
int rightSum = 0;
for (int i = n - 2; i >= 0; i--) {
rightSum += indices.get(i + 1);
result[indices.get(i)] += rightSum - (n - i - 1) * indices.get(i);
result[indices.get(i)] += leftTotalSum[i];
}
}
return result;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<int> sumOfDistances(const vector<int>& nums) {
unordered_map<int, vector<int>> value_to_indices;
for (int i = 0; i < nums.size(); ++i) {
value_to_indices[nums[i]].push_back(i);
}
vector<int> result(nums.size(), 0);
for (const auto& pair : value_to_indices) {
const auto& indices = pair.second;
int n = indices.size();
vector<int> leftTotalSum(n, 0);
int leftSum = 0;
for (int i = 1; i < n; ++i) {
leftSum += indices[i - 1];
leftTotalSum[i] = leftTotalSum[i - 1] + indices[i] - leftSum;
}
int rightSum = 0;
for (int i = n - 2; i >= 0; --i) {
rightSum += indices[i + 1];
result[indices[i]] += rightSum - (n - i - 1) * indices[i];
result[indices[i]] += leftTotalSum[i];
}
}
return result;
}function sumOfDistances(nums) {
const valueToIndices = {};
const result = Array(nums.length).fill(0);
nums.forEach((num, i) => {
if (!valueToIndices[num]) valueToIndices[num] = [];
valueToIndices[num].push(i);
});
Object.values(valueToIndices).forEach(indices => {
const n = indices.length;
const leftTotalSum = new Array(n).fill(0);
let leftSum = 0;
for (let i = 1; i < n; i++) {
leftSum += indices[i - 1];
leftTotalSum[i] = leftTotalSum[i - 1] + indices[i] - leftSum;
}
let rightSum = 0;
for (let i = n - 2; i >= 0; i--) {
rightSum += indices[i + 1];
result[indices[i]] += rightSum - (n - i - 1) * indices[i];
result[indices[i]] += leftTotalSum[i];
}
});
return result;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int[] SumOfDistances(int[] nums) {
var valueToIndices = new Dictionary<int, List<int>>();
for (int i = 0; i < nums.Length; i++) {
if (!valueToIndices.ContainsKey(nums[i])) {
valueToIndices[nums[i]] = new List<int>();
}
valueToIndices[nums[i]].Add(i);
}
int[] result = new int[nums.Length];
foreach (var indices in valueToIndices.Values) {
int n = indices.Count;
int[] leftTotalSum = new int[n];
int leftSum = 0;
for (int i = 1; i < n; i++) {
leftSum += indices[i-1];
leftTotalSum[i] = leftTotalSum[i-1] + indices[i] - leftSum;
}
int rightSum = 0;
for (int i = n - 2; i >= 0; i--) {
rightSum += indices[i+1];
result[indices[i]] += rightSum - (n - i - 1) * indices[i];
result[indices[i]] += leftTotalSum[i];
}
}
return result;
}
}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.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Default Approach
func distance(nums []int) []int64 {
n := len(nums)
ans := make([]int64, n)
d := map[int][]int{}
for i, x := range nums {
d[x] = append(d[x], i)
}
for _, idx := range d {
m := len(idx)
left, right := 0, -m*idx[0]
for _, i := range idx {
right += i
}
for i := range idx {
ans[idx[i]] = int64(left + right)
if i+1 < m {
left += (idx[i+1] - idx[i]) * (i + 1)
right -= (idx[i+1] - idx[i]) * (m - i - 1)
}
}
}
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
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.