Sum of Distances

MEDIUM

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.

Example 1:

Input: nums = [1,3,1,1,2]
Output: [5,0,3,4,0]
Explanation: 
When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5. 
When i = 1, arr[1] = 0 because there is no other index with value 3.
When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3. 
When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4. 
When i = 4, arr[4] = 0 because there is no other index with value 2.

Example 2:

Input: nums = [0,5,3]
Output: [0,0,0]
Explanation: Since each element in nums is distinct, arr[i] = 0 for all i.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Note: This question is the same as 2121: Intervals Between Identical Elements.

Approaches

Checkout 3 different approaches to solve Sum of Distances. Click on different approaches to view the approach and algorithm in detail.

Brute Force

The brute-force approach is the most straightforward way to solve the problem. It directly translates the problem description into code. We iterate through each element of the array and, for each element, we perform another full scan of the array to find all other elements with the same value. When a match is found at a different index, we calculate the absolute difference of the indices and add it to a running sum for the current element.

Algorithm

Initialize a result array arr of size n (length of nums) with zeros.
Iterate through the input array nums with an index i from 0 to n-1.
For each i, initialize a variable currentSum to 0.
Start a nested loop with an index j from 0 to n-1.
Inside the nested loop, check if i is not equal to j and if nums[i] is equal to nums[j].
If both conditions are true, calculate the absolute difference |i - j| and add it to currentSum.
After the inner loop completes, assign the value of currentSum to arr[i].
After the outer loop completes, return the arr.

This method involves using two nested loops. The outer loop iterates through each index i of the nums array, for which we want to calculate the sum of distances. The inner loop iterates through every other index j in the array. Inside the inner loop, we check if nums[j] is equal to nums[i]. If they are equal and i is not the same as j, we compute |i - j| and add it to a temporary sum. This sum is accumulated for all such j's. Once the inner loop finishes, the accumulated sum is the final value for arr[i]. This process is repeated for all indices i.

class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] arr = new long[n];

        for (int i = 0; i < n; i++) {
            long currentSum = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                if (nums[i] == nums[j]) {
                    currentSum += Math.abs(i - j);
                }
            }
            arr[i] = currentSum;
        }

        return arr;
    }
}

Complexity Analysis

Time Complexity: O(N^2) - For each of the N elements in the input array, we iterate through the entire array again. This results in N * N operations.Space Complexity: O(N) - We need an array of size N to store the results. If the output array is not considered, the space complexity is O(1).

Pros and Cons

Pros:

Simple to understand and implement.
Requires minimal auxiliary data structures.

Cons:

Extremely inefficient for large inputs due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Sum of Distances. Click on different languages to view the code.

class Solution {
public
  long[] distance(int[] nums) {
    int n = nums.length;
    long[] ans = new long[n];
    Map<Integer, List<Integer>> d = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      d.computeIfAbsent(nums[i], k->new ArrayList<>()).add(i);
    }
    for (var idx : d.values()) {
      int m = idx.size();
      long left = 0;
      long right = -1L * m * idx.get(0);
      for (int i : idx) {
        right += i;
      }
      for (int i = 0; i < m; ++i) {
        ans[idx.get(i)] = left + right;
        if (i + 1 < m) {
          left += (idx.get(i + 1) - idx.get(i)) * (i + 1L);
          right -= (idx.get(i + 1) - idx.get(i)) * (m - i - 1L);
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Sum of Distances

Patterns:

Prefix Sum

Data Structures:

ArrayHash Table

Companies:

BNY Mellon |