Problem Description

You are given a 0-indexed integer array nums. Your task is to create a new array arr of the same length as nums, where each element arr[i] represents a specific sum calculation.

For each position i in the array:

• Find all positions j where nums[j] == nums[i] and j != i (all other positions that have the same value as position i)
• Calculate the sum of absolute differences |i - j| for all such positions j
• Store this sum in arr[i]
• If no other position has the same value as nums[i], set arr[i] = 0

Example walkthrough:

If nums = [1, 3, 1, 1, 2]:

• For i = 0 (value is 1): Other positions with value 1 are at indices 2 and 3
  • arr[0] = |0 - 2| + |0 - 3| = 2 + 3 = 5
• For i = 1 (value is 3): No other position has value 3
  • arr[1] = 0
• For i = 2 (value is 1): Other positions with value 1 are at indices 0 and 3
  • arr[2] = |2 - 0| + |2 - 3| = 2 + 1 = 3
• For i = 3 (value is 1): Other positions with value 1 are at indices 0 and 2
  • arr[3] = |3 - 0| + |3 - 2| = 3 + 1 = 4
• For i = 4 (value is 2): No other position has value 2
  • arr[4] = 0

The result would be arr = [5, 0, 3, 4, 0].

Return the array arr.

Intuition

The naive approach would be to iterate through each position and find all other positions with the same value, calculating the sum of distances. However, this would be inefficient with O(n²) complexity.

The key insight is to group all indices by their values first. For each value that appears multiple times, we have a list of indices where it occurs. Now we need to efficiently calculate the sum of distances for each index in this group.

Consider a value that appears at indices [i₁, i₂, i₃, ..., iₖ]. For any index iⱼ in this list, we need to calculate:

• Sum of distances to all indices on its left: (iⱼ - i₁) + (iⱼ - i₂) + ... + (iⱼ - iⱼ₋₁)
• Sum of distances to all indices on its right: (iⱼ₊₁ - iⱼ) + (iⱼ₊₂ - iⱼ) + ... + (iₖ - iⱼ)

Instead of recalculating these sums from scratch for each position, we can use a sliding technique. As we move from one index to the next in our sorted list:

1. Initial calculation for the first index i₁: All other indices are to its right, so we calculate the sum of (i₂ - i₁) + (i₃ - i₁) + ... + (iₖ - i₁).

2. Moving from index iⱼ to iⱼ₊₁:

   • The left sum increases because all indices to the left are now further away by (iⱼ₊₁ - iⱼ). There are j indices to the left, so left sum increases by (iⱼ₊₁ - iⱼ) * j.
   • The right sum decreases because all indices to the right are now closer by (iⱼ₊₁ - iⱼ). There are (k - j - 1) indices to the right, so right sum decreases by (iⱼ₊₁ - iⱼ) * (k - j - 1).

This transformation allows us to update the sums in O(1) time as we traverse through each group, making the overall solution O(n) time complexity after the initial grouping.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation follows the intuition by using a dictionary to group indices and a sliding technique to efficiently calculate distances:

1. Group indices by value: Use a defaultdict(list) to store all indices for each unique value in nums. After iterating through the array, d[x] contains a list of all indices where value x appears.

2. Initialize result array: Create ans array of the same length as nums, initialized with zeros.

3. Process each group of indices: For each list of indices in the dictionary:

   • Initialize left = 0 (sum of distances to indices on the left)
   • Calculate initial right for the first index: sum(idx) - len(idx) * idx[0]
     • This represents the sum of distances from idx[0] to all other indices in the group
     • Mathematically: (idx[1] - idx[0]) + (idx[2] - idx[0]) + ... = sum(idx) - len(idx) * idx[0]

4. Traverse through each index in the group: For position i in the group:

   • Set ans[idx[i]] = left + right (total distance is sum of left and right distances)
   • Update for the next iteration (if not at the last index):
     • Update left: When moving from idx[i] to idx[i+1], all i+1 indices on the left become further by (idx[i+1] - idx[i]), so:
       • left += (idx[i+1] - idx[i]) * (i + 1)
     • Update right: The remaining len(idx) - i - 1 indices on the right become closer by the same distance, so:
       • right -= (idx[i+1] - idx[i]) * (len(idx) - i - 1)

5. Return the result: After processing all groups, return the ans array.

Time Complexity: O(n) where n is the length of the input array. We iterate through the array once to build the dictionary and once more to calculate distances.

Space Complexity: O(n) for the dictionary and result array.

Example Walkthrough

Let's walk through a smaller example to illustrate the solution approach clearly.

Given nums = [2, 1, 2, 1]:

Step 1: Group indices by value

• Value 1 appears at indices: [1, 3]
• Value 2 appears at indices: [0, 2]

Step 2: Process group with value 2 (indices [0, 2])

For index 0:

• Initialize: left = 0 (no indices to the left)
• Calculate right = sum([0, 2]) - 2 * 0 = 2 - 0 = 2
  • This represents the distance from index 0 to index 2: |0 - 2| = 2
• Set ans[0] = left + right = 0 + 2 = 2
• Update for next iteration:
  • left = 0 + (2 - 0) * 1 = 2 (1 index now on the left, distance increased by 2)
  • right = 2 - (2 - 0) * 1 = 0 (1 index on the right became closer by 2)

For index 2:

• Current: left = 2, right = 0
• Set ans[2] = left + right = 2 + 0 = 2

Step 3: Process group with value 1 (indices [1, 3])

For index 1:

• Initialize: left = 0
• Calculate right = sum([1, 3]) - 2 * 1 = 4 - 2 = 2
  • This represents the distance from index 1 to index 3: |1 - 3| = 2
• Set ans[1] = left + right = 0 + 2 = 2
• Update for next iteration:
  • left = 0 + (3 - 1) * 1 = 2
  • right = 2 - (3 - 1) * 1 = 0

For index 3:

• Current: left = 2, right = 0
• Set ans[3] = left + right = 2 + 0 = 2

Final Result: ans = [2, 2, 2, 2]

Each element correctly represents the sum of distances to all other positions with the same value. The sliding technique allows us to calculate these sums efficiently without recalculating from scratch for each position.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

• Creating the dictionary d with indices grouped by values takes O(n) time as we iterate through the array once.
• For the main computation, we iterate through each group of indices in d.values().
• For each group of indices with length k, we perform:
  • Initial calculation of right: O(k) time for the sum
  • Iteration through the group: O(k) operations
• Since the total number of indices across all groups equals n, the overall time complexity is O(n).

Space Complexity: O(n)

• The dictionary d stores all indices, which requires O(n) space in the worst case.
• The answer array ans requires O(n) space.
• Other variables (left, right, loop variables) use O(1) space.
• Therefore, the total space complexity is O(n).

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

Common Pitfalls

1. Incorrect Distance Calculation for Groups

A common mistake is trying to calculate distances naively by iterating through all pairs, leading to O(n²) complexity for groups with many duplicate values.

Pitfall Example:

# Inefficient approach that times out on large inputs
for i in range(len(nums)):
    total = 0
    for j in range(len(nums)):
        if i != j and nums[i] == nums[j]:
            total += abs(i - j)
    result[i] = total

Solution: Use the sliding window technique shown in the optimal solution, maintaining running sums of left and right distances.

2. Off-by-One Errors in Index Counting

When updating left_sum and right_sum, it's easy to miscount how many indices are on each side.

Pitfall Example:

# Wrong: Using i instead of (i + 1) for left count
left_sum += gap * i  # Should be (i + 1)
# Wrong: Using (len(indices) - i) instead of (len(indices) - i - 1)
right_sum -= gap * (len(indices) - i)  # Should be (len(indices) - i - 1)

Solution: Remember that:

• After processing index i, there are exactly (i + 1) indices on the left (including all previous ones)
• There are (len(indices) - i - 1) indices remaining on the right (excluding current)

3. Incorrect Initial Right Sum Calculation

The initial right_sum calculation can be confusing and prone to errors.

Pitfall Example:

# Wrong: Forgetting to multiply by the first index position
right_sum = sum(indices) - len(indices)  # Missing multiplication by indices[0]
# Wrong: Using wrong formula
right_sum = sum(indices[1:]) - indices[0] * (len(indices) - 1)  # Incorrect

Solution: The correct formula is sum(indices) - len(indices) * indices[0], which represents the sum of all distances from indices[0] to every other index in the group.

4. Not Handling Single-Element Groups

While the code handles this correctly (left_sum = 0, right_sum = 0), it's easy to overlook that groups with only one element should result in 0.

Solution: The algorithm naturally handles this case since the loop runs once with both left_sum and right_sum as 0, but be mindful when modifying the code.