Sum of Distances

Medium
1173.

Sum of Distances

Sum of Distances is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

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^4
  • 0 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var distance = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 0 <= nums[i] <= 10^9

Hints for Sum of Distances

  1. Hint 1

    Only indices holding the same value interact, so handle each value's list of positions separately.

  2. Hint 2

    For a position p with c equal values to its left whose indices sum to s, their contribution is c * p - s.

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

  1. Left-to-right: for each i with value v, add cnt[v] * i - sum[v] to arr[i], then increment cnt[v] and add i to sum[v].
  2. Reset the maps.
  3. Right-to-left: for each i, add sum[v] - cnt[v] * i to arr[i], then update cnt[v] and sum[v].
  4. 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 * i can 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 res

Java

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