We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Distances

Number: 2721

Difficulty: Medium

Paid? No

Companies: Google, Meta, BNY Mellon

Problem Description

Given an integer array nums, for every index i compute the sum of the absolute differences |i - j| for all indices j (j ≠ i) where nums[j] equals nums[i]. If no such j exists, the result for index i is 0. Return the resulting array.

Key Insights

  • Group indices by their corresponding values using a hash table.
  • For each group of indices (which are naturally in sorted order), precompute prefix sums of indices for efficient range sum calculations.
  • For each index at position i within the group, the sum of distances can be computed using:
    • Left contribution: i * current_index - (sum of indices up to i-1)
    • Right contribution: (sum of indices from i+1 to end) - (number_of_elements_after_i * current_index)
  • Process each group independently and assign the computed value to the correct positions in the answer array.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array (each index is processed once and prefix sums are computed in linear time per group). Space Complexity: O(n) to store the groups and prefix sum arrays.

Solution

We utilize a hash table (or dictionary) to group indices by the value in nums. For each group, we compute a prefix sum of indices. For an index at position i within a group with sorted indices, the distance sum is calculated as:

left_dist = (current_index * i) - (sum of all indices before i)
right_dist = (sum of all indices after i) - (current_index * (number of indices after i))

Adding left_dist and right_dist gives the total sum of distances for that index. We then place this result back into the output array at the proper index.

Code Solutions

# Python solution for the "Sum of Distances" problem

def getDistances(nums):
    from collections import defaultdict
    # Dictionary to map each number to its list of indices
    index_map = defaultdict(list)
    for idx, num in enumerate(nums):
        index_map[num].append(idx)
    
    # Initialize result array with zeros
    result = [0] * len(nums)
    
    # Process each group of indices
    for indices in index_map.values():
        n = len(indices)
        if n <= 1:
            continue  # No pair exists, so skip
        # Precompute prefix sums for the current group of indices
        prefix_sum = [0] * n
        prefix_sum[0] = indices[0]
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i - 1] + indices[i]
        
        # Calculate the sum of distances for each index in the group using the prefix sums
        for i in range(n):
            current = indices[i]
            # Left contribution: distances from indices before current
            left = current * i - (prefix_sum[i - 1] if i > 0 else 0)
            # Right contribution: distances from indices after current
            right = (prefix_sum[n - 1] - prefix_sum[i]) - current * (n - i - 1)
            # Total distance is the sum of left and right contributions
            result[current] = left + right
    return result

# Example usage:
# nums = [1,3,1,1,2]
# print(getDistances(nums))  # Output should be [5, 0, 3, 4, 0]
← Back to All Questions