Problem Description

You have an array arr of n integers indexed from 0 to n-1. For each element in the array, you need to calculate the sum of distances (intervals) between that element and all other elements in the array that have the same value.

The distance (interval) between two elements at positions i and j is defined as the absolute difference of their indices: |i - j|.

Your task is to return an array intervals where intervals[i] contains the sum of all distances from arr[i] to every other element in arr that has the same value as arr[i].

For example:

• If arr = [2, 1, 3, 1, 2, 3, 3]
• For the element at index 0 (value 2), you need to find all other positions with value 2 (which is index 4), and calculate |0 - 4| = 4
• For the element at index 1 (value 1), you need to find all other positions with value 1 (which is index 3), and calculate |1 - 3| = 2
• For the element at index 2 (value 3), you need to find all other positions with value 3 (indices 5 and 6), and calculate |2 - 5| + |2 - 6| = 3 + 4 = 7

The solution groups indices by their values using a dictionary, then efficiently calculates the sum of intervals for each group. For each group of identical values, it uses a mathematical approach to compute the sum of distances by maintaining a running sum (val) and updating it based on the position changes, avoiding the need to recalculate all distances for each element.

Intuition

The naive approach would be to iterate through each element and find all other elements with the same value, calculating the distance to each one. This would take O(n²) time, which is inefficient for large arrays.

The key insight is that we can group all indices by their values first. For elements with the same value, we need to calculate the sum of distances efficiently without recalculating everything from scratch for each position.

Consider elements with the same value at positions [p₀, p₁, p₂, ..., pₘ₋₁]. For the element at position pᵢ, the sum of distances is: |pᵢ - p₀| + |pᵢ - p₁| + ... + |pᵢ - pₘ₋₁|

Since the positions are sorted, for element at pᵢ:

• Elements to the left (p₀ to pᵢ₋₁) contribute: (pᵢ - p₀) + (pᵢ - p₁) + ... + (pᵢ - pᵢ₋₁) = i * pᵢ - (p₀ + p₁ + ... + pᵢ₋₁)
• Elements to the right (pᵢ₊₁ to pₘ₋₁) contribute: (pᵢ₊₁ - pᵢ) + (pᵢ₊₂ - pᵢ) + ... + (pₘ₋₁ - pᵢ) = (pᵢ₊₁ + ... + pₘ₋₁) - (m - i - 1) * pᵢ

The brilliant optimization comes from recognizing that when we move from position pᵢ₋₁ to pᵢ, we can update the sum incrementally. The difference delta = pᵢ - pᵢ₋₁ affects the sum in a predictable way:

• The i elements to the left now have their distances increased by delta each, contributing +i * delta
• The (m - i) elements to the right (including current) have their distances decreased by delta each, contributing -(m - i) * delta

This allows us to maintain a running sum val and update it in O(1) time for each element, reducing the overall complexity to O(n) after the initial grouping.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation uses a dictionary to group indices by their values, then applies the mathematical optimization discussed in the intuition.

Step 1: Group indices by values

d = defaultdict(list)
for i, v in enumerate(arr):
    d[v].append(i)

We create a dictionary where each key is a value from the array, and the corresponding value is a list of all indices where that value appears.

Step 2: Initialize the result array

ans = [0] * n

Step 3: Process each group of identical values For each group of indices v in the dictionary:

m = len(v)  # number of elements with this value
val = sum(v) - v[0] * m  # initial sum for the first element

The initial val for the first position v[0] is calculated as:

• sum(v) gives us the sum of all positions
• v[0] * m is subtracted because for the first element, all distances are (v[1] - v[0]) + (v[2] - v[0]) + ... + (v[m-1] - v[0])
• This simplifies to (v[1] + v[2] + ... + v[m-1]) - (m-1) * v[0]
• Which equals sum(v) - v[0] * m

Step 4: Calculate sums for remaining positions in the group

for i, p in enumerate(v):
    delta = v[i] - v[i - 1] if i >= 1 else 0
    val += i * delta - (m - i) * delta
    ans[p] = val

For each position after the first:

• Calculate delta: the distance moved from the previous position
• Update val using the formula: val += i * delta - (m - i) * delta
  • i * delta: increase from the i elements now to our left
  • (m - i) * delta: decrease from the (m - i) elements to our right (including current)
• Store the computed sum at the appropriate index in the answer array

Time Complexity: O(n) - we visit each element once for grouping and once for calculation Space Complexity: O(n) - for the dictionary storing the grouped indices and the answer array

Example Walkthrough

Let's walk through a small example with arr = [2, 1, 3, 1, 2].

Step 1: Group indices by values

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

Our dictionary d becomes:

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

Step 2: Process each group

Group with value 1: indices [1, 3]

• m = 2 (two elements with value 1)
• Initial sum for index 1: val = sum([1, 3]) - 1 * 2 = 4 - 2 = 2
  • This represents the distance from index 1 to index 3: |1 - 3| = 2
• ans[1] = 2

For index 3:

• delta = 3 - 1 = 2 (moved 2 positions from previous)
• val = 2 + 1 * 2 - (2 - 1) * 2 = 2 + 2 - 2 = 2
  • The 1 element to the left (index 1) is now 2 units farther: +2
  • The 1 element at/right (current position) is 2 units closer: -2
• ans[3] = 2

Group with value 2: indices [0, 4]

• m = 2 (two elements with value 2)
• Initial sum for index 0: val = sum([0, 4]) - 0 * 2 = 4 - 0 = 4
  • This represents the distance from index 0 to index 4: |0 - 4| = 4
• ans[0] = 4

For index 4:

• delta = 4 - 0 = 4 (moved 4 positions from previous)
• val = 4 + 1 * 4 - (2 - 1) * 4 = 4 + 4 - 4 = 4
  • The 1 element to the left (index 0) is now 4 units farther: +4
  • The 1 element at/right (current position) is 4 units closer: -4
• ans[4] = 4

Group with value 3: indices [2]

• m = 1 (only one element with value 3)
• Initial sum for index 2: val = sum([2]) - 2 * 1 = 2 - 2 = 0
  • No other elements with value 3, so sum is 0
• ans[2] = 0

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

We can verify:

• ans[0]: distance from arr[0]=2 to arr[4]=2 is |0-4| = 4 ✓
• ans[1]: distance from arr[1]=1 to arr[3]=1 is |1-3| = 2 ✓
• ans[2]: no other 3s in the array, sum = 0 ✓
• ans[3]: distance from arr[3]=1 to arr[1]=1 is |3-1| = 2 ✓
• ans[4]: distance from arr[4]=2 to arr[0]=2 is |4-0| = 4 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main phases:

1. Building the dictionary d by iterating through the array once: O(n)
2. For each unique value in the dictionary:
   • Initial sum calculation for the first position: O(m) where m is the number of occurrences of that value
   • Iterating through all positions of that value to calculate distances: O(m)

Since we process each element exactly once in the second phase (as each index appears in exactly one list in the dictionary), the total work done across all unique values is O(n). Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The space usage includes:

• Dictionary d: stores indices for each unique value, totaling O(n) space across all lists
• Answer array ans: O(n) space
• Variables val, delta, and other constants: O(1) space

The total space complexity is O(n) + O(n) + O(1) = O(n).

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

Common Pitfalls

1. Incorrect Initial Sum Calculation

A common mistake is incorrectly calculating the initial sum for the first element in each group. Developers often try:

# WRONG: This doesn't give the sum of distances from first element
current_sum = sum(indices[1:]) - indices[0] * (count - 1)

Why it's wrong: The formula should account for all indices including the first one, then subtract appropriately.

Correct approach:

# Sum of all indices minus first index times total count
current_sum = sum(indices) - indices[0] * count

2. Off-by-One Error in Delta Update Formula

When updating the sum for subsequent positions, a frequent error is using the wrong counts:

# WRONG: Using (count - i - 1) instead of (count - i)
current_sum += i * index_diff - (count - i - 1) * index_diff

Why it's wrong: When at position i, there are exactly i elements to the left and count - i elements at or to the right (including current position).

Correct formula:

current_sum += i * index_diff - (count - i) * index_diff

3. Not Handling Single-Element Groups

The code might break or produce incorrect results if not properly handling groups with only one element:

# Potential issue if not careful with single-element groups
for indices in value_to_indices.values():
    if len(indices) == 1:
        # Should set result[indices[0]] = 0, not skip
        continue  # WRONG: This would leave the result as uninitialized

Solution: The current implementation handles this correctly since:

• For single-element groups, current_sum becomes 0 naturally
• The loop executes once and sets result[indices[0]] = 0

4. Using Nested Loops for Distance Calculation

A naive approach that recalculates all distances for each element:

# WRONG: O(n²) time complexity in worst case
for i, current_index in enumerate(indices):
    total = 0
    for j, other_index in enumerate(indices):
        if i != j:
            total += abs(current_index - other_index)
    result[current_index] = total

Why it's inefficient: This has O(k²) complexity for each group of k elements, leading to O(n²) in the worst case when all elements are identical.

Solution: Use the mathematical optimization with running sum as shown in the correct implementation, achieving O(n) overall complexity.