How do you solve Sum of Distances on LeetCode?

Sum of Distances (LeetCode #2615) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a hashmap allows us to group indices efficiently.

What is the brute force solution for Sum of Distances?

The brute force approach for Sum of Distances is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we calculate the sum of distances for each index by checking every other index with the same value. This is straightforward but inefficient for large arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Sum of Distances?

Sum of Distances uses the following concepts: Array, Hash Table, Prefix Sum. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Sum of Distances?

Think about how to reduce the number of operations by grouping similar elements. Always consider edge cases, such as arrays with all distinct elements. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Sum of Distances?

Not using a hashmap to group indices, leading to unnecessary repeated calculations. Forgetting to handle cases where there are no duplicates.

#2615

Sum of Distances

Medium

ArrayHash TablePrefix SumHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a hashmap to group indices of identical elements and calculates the sum of distances using prefix sums, which significantly reduces the time complexity.

⚙️

Algorithm

4 steps

1Step 1: Create a hashmap to store indices of each unique number in 'nums'.
2Step 2: For each unique number, calculate the prefix sums of the indices.
3Step 3: For each index, use the prefix sums to compute the total distance to all other indices with the same number.
4Step 4: Store the results in the 'arr' array.

solution.py19 lines

1def sum_of_distances(nums):
2    from collections import defaultdict
3    n = len(nums)
4    arr = [0] * n
5    index_map = defaultdict(list)
6    for i, num in enumerate(nums):
7        index_map[num].append(i)
8    for indices in index_map.values():
9        prefix_sum = [0] * (len(indices) + 1)
10        for i in range(1, len(indices) + 1):
11            prefix_sum[i] = prefix_sum[i - 1] + indices[i - 1]
12        total = 0
13        for i in range(len(indices)):
14            left_count = i
15            right_count = len(indices) - i - 1
16            total += indices[i] * right_count - (prefix_sum[len(indices)] - prefix_sum[i + 1])
17            total += (prefix_sum[i] - prefix_sum[0]) - indices[i] * left_count
18            arr[indices[i]] = total
19    return arr

ℹ

Complexity note: This complexity is due to the single pass through the array to build the hashmap and another pass through the indices to calculate distances, making it linear.

1Using a hashmap allows us to group indices efficiently.
2Prefix sums help in calculating distances in linear time.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.