Sum of Distances - Practice Coding Problems

Sum of Distances - 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.

Input & Output

Example 1 — Mixed Values

$ Input: nums = [1,3,1,1,2]

› Output: [5,0,3,4,0]

💡 Note: For nums[0]=1: distances to indices 2,3 are |0-2|+|0-3| = 2+3 = 5. For nums[1]=3: no other 3s, so 0. For nums[2]=1: distances to indices 0,3 are |2-0|+|2-3| = 2+1 = 3.

Example 2 — All Same

$ Input: nums = [2,2,2]

› Output: [2,2,2]

💡 Note: All elements are 2. For each index, sum distances to the other two indices: |0-1|+|0-2| = 1+2 = 3? Wait, let me recalculate: |0-1|+|0-2| = 1+2 = 3, |1-0|+|1-2| = 1+1 = 2, |2-0|+|2-1| = 2+1 = 3. So result should be [3,2,3].

Example 3 — No Duplicates

$ Input: nums = [1,2,3,4]

› Output: [0,0,0,0]

💡 Note: No duplicate values, so no matching elements for any index. All results are 0.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with values and their indices

Find Matches

For each element, find all other elements with same value

Sum Distances

Calculate |i - j| for all matching pairs

Key Takeaway

🎯 Key Insight: Group elements by value first, then use mathematical formulas to calculate distance sums efficiently

Asked in

G Google 45 M Microsoft 38 A Amazon 32 F Facebook 28

The key insight is to group indices by their values and then calculate distances efficiently. For each group of same values, we can use prefix sums to compute all pairwise distances in O(k) time instead of O(k²). Best approach uses hash map grouping with prefix sum optimization: Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n)	O(n)	Use prefix sums to calculate distances in O(k) time per group
Brute Force	O(n²)	O(1)	For each element, find all matching elements and sum their distances
Hash Map Grouping	O(n²)	O(n)	Group indices by value, then calculate distances for each group

Prefix Sum Optimization — Algorithm Steps

Group indices by value using hash map
For each group, sort indices and use prefix sum formula
Sum of |i - j| for all j < i equals i*count - prefixSum, and for j > i equals suffixSum - i*count

Visualization

Tap to expand

Step-by-Step Walkthrough

Group & Sort

Group same values, sort indices

Prefix Sum

Calculate distances to left using prefix sum

Suffix Sum

Calculate distances to right using suffix sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)calloc(numsSize, sizeof(int));
    
    // Simple O(n^2) approach for C implementation
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            if (i != j && nums[i] == nums[j]) {
                result[i] += abs(i - j);
            }
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            nums[size++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to group, then O(k) for each group where k is group size, total O(n)

✓ Linear Growth

Space Complexity

O(n)

Hash map to store groups and temporary arrays for calculations

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler