2615. Sum of Distances

Problem Description

In this problem, we're presented with an integer array nums which is 0-indexed. We're tasked to find another array arr where each element arr[i] represents the sum of absolute differences between index i and every index j where the value nums[j] is equal to nums[i], excluding when i and j are the same. If there are no such j values (meaning there are no other identical values to nums[i] in the array), we simply set arr[i] to 0.

To illustrate, if nums was [3, 3, 1], then arr would be [1, 1, 0] because:

• For i=0, nums[0] == 3, we find another 3 at index 1, so the sum is |0 - 1| = 1. There are no more 3s, so arr[0] is 1.
• For i=1, it's the same situation but in reverse, so arr[1] is also 1.
• For i=2, nums[2] == 1 and there are no other 1s in the array, so arr[2] is 0.

We need to perform this calculation efficiently for each index and construct the arr array accordingly.

Intuition

To find an effective solution, we should try to avoid the naive approach of checking each pair of indices for equality, as that would result in an O(n^2) time complexity, which is impractical for large arrays.

Instead, we can optimize by grouping indices with the same values together. We can use a dictionary to map each unique number in the array to the list of indices where that number appears. This will help us compute the sum of distances for each group in aggregate, rather than individually.

Once we have those index lists, we can iterate over them to calculate the sum of distances for each index in the group. Here's the step-by-step approach:

1. We compute the sum of indices for each group - this gives us a starting sum for the right part of each index.
2. We start from the leftmost index in each group and iterate towards the right.
3. For each index, we maintain two variables: left and right, which represent the sum of distances to indices on the left and right, respectively.
4. As we move from one index to the next within a group, we update left by adding the distance to the next index multiplied by the count of indices that are now on the left.
5. We update right by subtracting the same distance multiplied by the count of indices remaining on the right.
6. We use these left and right accumulators to calculate the total distance for each index, this total distance is what we add to the corresponding position in the arr array.

This approach reduces the amount of redundant calculations and brings the complexity down significantly because each distance is essentially calculated in linear time relative to the number of occurrences of each unique value.

Learn more about Prefix Sum patterns.

Solution Approach

The solution utilizes a hash map (via Python's defaultdict from the collections module) to group the indices of identical values in nums. Here's how the solution is implemented:

1. Initialize a defaultdict of lists named d. Iterate over nums using enumerate to build the dictionary where each key is a value in nums, and the corresponding value is a list of indices where that key appears.

2. Create an array ans filled with zeros of the same length as nums. This array will store our resulting distances for each index.

3. For each list of indices idx in the hash map:

   • Initialize left as 0 because there are no indices to the left of our starting point.
   • Calculate the initial value of right by summing up all the indices in idx and adjusting for the lowest index (len(idx) * idx[0]). This variable represents the sum of distances of all indices to the right of our current index.

4. Iterate over each index i in idx:

   • Set ans[idx[i]] to be the sum of left plus right, which provides the sum of distances for nums[idx[i]].
   • Before we move to the next index i+1, we update left and right. Update left by adding the distance to the next index multiplied by i + 1 (because we'll have one more element to the left).
   • Update right by subtracting the same distance multiplied by (len(idx) - i - 1) to account for having one less element to the right.

5. Loop until all indices in idx are processed. By the end, ans will have the calculated distances for each element in nums.

This approach is efficient because it computes the distances for indices of the same value in nums as a whole, minimizing repeated work. By using left and right accumulators, it avoids iterating over all pairs of indices and scales linearly with the number of occurrences of each unique value in nums.

The algorithmic patterns used here include hashing (to group indices), enumeration (to iterate with indices), and prefix sums (though not explicitly stored, they are implied in the use of left and right to keep track of cumulative distances).

Example Walkthrough

For illustration, let's use nums = [2, 1, 2, 1, 2] to demonstrate the solution approach.

1. We first create the hash map with the list of indices for each value in nums:

   For value 2, the list of indices is [0, 2, 4]. For value 1, the list of indices is [1, 3].

   Our hash map (d) now looks like this:

   1{
   2    2: [0, 2, 4],
   3    1: [1, 3]
   4}

2. We then initialize the ans array to [0, 0, 0, 0, 0], corresponding to the five elements in nums.

3. We begin processing the list of indices for the value 2:

   • Initial setup for value 2: left = 0, right is calculated by (2 + 4) - (2 * 0) = 6.

   • First index (i=0):

     • We set ans[0] = left + right → ans[0] = 0 + 6 = 6.
     • We update left to be 0 + (1 * 2) since we're moving one step to the right, adding two spaces (distance) from the first index.
     • We update right by subtracting 2 * (3 - 1 - 0) to account for the two spaces we're moving away from the remaining two indices (2 and 4).

   • Second index (i=1):

     • Now left = 2 and right = 2 (from previous calculations).
     • Thus, ans[2] = left + right → ans[2] = 2 + 2 = 4.
     • Update left to be 2 + (2 * 2) as we're now considering the total distance from the first and second index to the third.
     • Update right to be 2 - (2 * (2 - 1 - 1)), no change because only one index remains to the right, and we're moving one step away from it.

   • Third index (i=2):

     • Now left = 6 and right = 0 (there are no more indices to the right).
     • So, ans[4] = left + right → ans[4] = 6 + 0 = 6.

   With value 2 processed, ans becomes [6, 0, 4, 0, 6].

4. Next, proceed with the indices for value 1:

   • Initial setup for value 1: left = 0, right is calculated by (3) - (1 * 1) = 2.

   • First index (i=0):

     • ans[1] = left + right → ans[1] = 0 + 2 = 2.
     • Update left to be 0 + (1 * 1),
     • Update right to be 2 - (1 * (2 - 1 - 0)), which makes right = 1 now.

   • Second index (i=1):

     • left = 1 and right = 0.
     • ans[3] = left + right → ans[3] = 1 + 0 = 1.

   Now, our answer array ans is completely updated to [6, 2, 4, 1, 6].

After processing both lists of indices, we get arr = [6, 2, 4, 1, 6] corresponding to the sum of absolute differences for each index in nums, as intended by the solution approach.

Solution Implementation

Time and Space Complexity

The above code maintains a dictionary to store indices of each unique element in the list nums and then computes the distance sum for each unique element.

Time Complexity:

• The first for loop iterates over all n elements of the list nums to create the dictionary d, which takes O(n) time.
• The second loop processes each group of indices stored in the dictionary d. Let k be the maximum size of these index groups. For each group, it iterates over all elements in the list of indices which, in the worst case, could take O(k). Since there are as many groups as there are unique elements in nums, we can say that it takes O(u * k) time, where u is the number of unique elements.
• Inside this loop, it performs constant-time operations like addition and subtraction for updating left and right variables.

Since k times the number of unique elements u cannot exceed n (as each element is part of one group and is visited once), the second loop's time complexity is bounded by O(n).

Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity:

• The space taken by the dictionary d depends on the number of unique elements in nums. If there are u unique elements, it could take up to O(u * k) space, where k is the average size of the index lists for each unique element. However, since there are n total elements, u * k is also bounded by n. Therefore, it uses O(n) space.
• We also have the ans array, which is equal in size to nums, adding another O(n) space.

Adding these together, the space complexity of the code is O(n) + O(n) = O(n).

Learn more about how to find time and space complexity quickly using problem constraints.