Sum of Distances — Solution in Python, Java & C++
Sum of Distances solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Distances is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For each index i of the 0-indexed integer array nums, let arr[i] be the sum of |i - j| over every other index j with nums[j] == nums[i]. If nums[i] occurs nowhere else, arr[i] = 0.
Return arr.
Note: the original problem allows 10^5 elements and returns 64-bit sums; here nums.length <= 5 * 10^4, so every answer fits in a 32-bit integer.
Example 1
Input: nums = [2,5,2,2,5]
Output: [5,3,3,4,3]
Explanation: The value 2 sits at indices 0, 2 and 3: index 0 gets 2 + 3 = 5, index 2 gets 2 + 1 = 3, index 3 gets 3 + 1 = 4. The value 5 sits at 1 and 4, three apart.
Example 2
Input: nums = [7,8,9]
Output: [0,0,0]
Constraints
1 <= nums.length <= 5 * 10^40 <= nums[i] <= 10^9
Hints for Sum of Distances
Hint 1
Only indices holding the same value interact, so handle each value's list of positions separately.
Hint 2
For a position
pwithcequal values to its left whose indices sum tos, their contribution isc * p - s.Hint 3
Sweep left to right accumulating (count, sum) per value, then right to left for the other side.
How to solve Sum of Distances
The distances to equal values on the left of i add up to count_left * i - sum_left, and those on the right to sum_right - count_right * i. Two sweeps with per-value running counts and index sums give both in O(1) per index.
Approach
- Left-to-right: for each
iwith valuev, addcnt[v] * i - sum[v]toarr[i], then incrementcnt[v]and additosum[v]. - Reset the maps.
- Right-to-left: for each
i, addsum[v] - cnt[v] * itoarr[i], then updatecnt[v]andsum[v]. - Return
arr.
Why it works
Every equal index to the left of i is smaller than i, so Σ (i - j) = c·i - Σ j over exactly those c indices, which the left sweep has accumulated when it reaches i. The right sweep is the mirror image. Together they cover every other index holding the same value once.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Intermediate products like
cnt * ican exceed 32 bits even when the final answer fits — use 64-bit arithmetic. - The value itself never enters the sum, only indices.
- A value that occurs once gives 0.
Reference solution
Python
from typing import List
def distance(nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
cnt, tot = {}, {}
for i in range(n):
v = nums[i]
c, s = cnt.get(v, 0), tot.get(v, 0)
res[i] += c * i - s
cnt[v], tot[v] = c + 1, s + i
cnt, tot = {}, {}
for i in range(n - 1, -1, -1):
v = nums[i]
c, s = cnt.get(v, 0), tot.get(v, 0)
res[i] += s - c * i
cnt[v], tot[v] = c + 1, s + i
return resJava
public static int[] distance(int[] nums) {
int n = nums.length;
long[] res = new long[n];
Map<Integer, long[]> left = new HashMap<>();
for (int i = 0; i < n; i++) {
long[] cs = left.computeIfAbsent(nums[i], key -> new long[2]);
res[i] += cs[0] * i - cs[1];
cs[0]++;
cs[1] += i;
}
Map<Integer, long[]> right = new HashMap<>();
for (int i = n - 1; i >= 0; i--) {
long[] cs = right.computeIfAbsent(nums[i], key -> new long[2]);
res[i] += cs[1] - cs[0] * i;
cs[0]++;
cs[1] += i;
}
int[] out = new int[n];
for (int i = 0; i < n; i++) out[i] = (int) res[i];
return out;
}C++
vector<int> distance(vector<int>& nums) {
int n = nums.size();
vector<long long> res(n, 0);
unordered_map<int, pair<long long, long long>> left, right;
for (int i = 0; i < n; i++) {
auto& cs = left[nums[i]];
res[i] += cs.first * i - cs.second;
cs.first++;
cs.second += i;
}
for (int i = n - 1; i >= 0; i--) {
auto& cs = right[nums[i]];
res[i] += cs.second - cs.first * i;
cs.first++;
cs.second += i;
}
vector<int> out(n);
for (int i = 0; i < n; i++) out[i] = (int)res[i];
return out;
}JavaScript
var distance = function(nums) {
var n = nums.length;
var res = new Array(n).fill(0);
var cnt = new Map(), tot = new Map();
for (var i = 0; i < n; i++) {
var v = nums[i];
var c = cnt.get(v) || 0, s = tot.get(v) || 0;
res[i] += c * i - s;
cnt.set(v, c + 1);
tot.set(v, s + i);
}
cnt = new Map();
tot = new Map();
for (var j = n - 1; j >= 0; j--) {
var w = nums[j];
var c2 = cnt.get(w) || 0, s2 = tot.get(w) || 0;
res[j] += s2 - c2 * j;
cnt.set(w, c2 + 1);
tot.set(w, s2 + j);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets