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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Distances

Difficulty: Medium

Problem Description

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.

Key Insights

  • For each index i, we need to calculate the sum of distances to all other indices j where nums[j] is equal to nums[i].
  • A direct approach using nested loops would lead to O(n^2) time complexity, which is inefficient for large input sizes.
  • Instead, we can use a more efficient method by grouping indices of identical elements and leveraging prefix sums to calculate distances.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n)

Solution

To solve the problem, we can follow these steps:

  1. Use a hash table to group indices of identical elements in nums.
  2. For each group of indices:
    • Calculate the total distance for each index using the prefix sum technique.
    • The distance can be computed efficiently by maintaining a running sum of indices and the number of occurrences.
  3. Store the results in the arr array.

This approach minimizes the number of operations needed to compute the distances by avoiding redundant calculations.

Code Solutions

def sum_of_distances(nums):
    from collections import defaultdict
    
    index_map = defaultdict(list)
    n = len(nums)
    arr = [0] * n
    
    # Group indices of identical elements
    for i in range(n):
        index_map[nums[i]].append(i)
    
    # Calculate distances for each group
    for indices in index_map.values():
        total_indices = len(indices)
        if total_indices < 2:
            continue
        
        prefix_sum = [0] * total_indices
        prefix_sum[0] = indices[0]
        
        # Prepare prefix sums
        for i in range(1, total_indices):
            prefix_sum[i] = prefix_sum[i - 1] + indices[i]
        
        # Calculate distances
        for i in range(total_indices):
            left_count = i
            right_count = total_indices - i - 1
            
            left_sum = indices[i] * left_count - (prefix_sum[i - 1] if left_count > 0 else 0)
            right_sum = (prefix_sum[total_indices - 1] - prefix_sum[i]) - indices[i] * right_count
            
            arr[indices[i]] = left_sum + right_sum
    
    return arr
← Back to All Questions