2615. Sum of Distances LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2615. Sum of Distances LeetCode Solution with the best time and space complexity. The solution to Sum of Distances problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sum of Distances solution in C++
Sum of Distances solution in Java
Sum of Distances solution in Python
Additional Resources

2615. Sum of Distances LeetCode Solution image

Problem Statement of Sum of Distances

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 <= 105
0 <= nums[i] <= 109

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2615. Sum of Distances LeetCode Solution in C++

class Solution {
 public:
  vector<long long> distance(vector<int>& nums) {
    vector<long long> ans(nums.size());
    unordered_map<int, vector<int>> numToIndices;

    for (int i = 0; i < nums.size(); ++i)
      numToIndices[nums[i]].push_back(i);

    for (const auto& [_, indices] : numToIndices) {
      const int n = indices.size();
      if (n == 1)
        continue;
      long sumSoFar = accumulate(indices.begin(), indices.end(), 0L);
      int prevIndex = 0;
      for (int i = 0; i < n; ++i) {
        sumSoFar += (i - 1) * (indices[i] - prevIndex);
        sumSoFar -= (n - 1 - i) * (indices[i] - prevIndex);
        ans[indices[i]] = sumSoFar;
        prevIndex = indices[i];
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2615. Sum of Distances LeetCode Solution in Java

class Solution {
  public long[] distance(int[] nums) {
    long[] ans = new long[nums.length];
    Map<Integer, List<Integer>> numToIndices = new HashMap<>();

    for (int i = 0; i < nums.length; ++i) {
      numToIndices.putIfAbsent(nums[i], new ArrayList<>());
      numToIndices.get(nums[i]).add(i);
    }

    for (List<Integer> indices : numToIndices.values()) {
      final int n = indices.size();
      if (n == 1) {
        continue;
      }
      long sumSoFar = indices.stream().mapToLong(Integer::intValue).sum();
      int prevIndex = 0;
      for (int i = 0; i < n; ++i) {
        sumSoFar += (i - 1) * (indices.get(i) - prevIndex);
        sumSoFar -= (n - 1 - i) * (indices.get(i) - prevIndex);
        ans[indices.get(i)] = sumSoFar;
        prevIndex = indices.get(i);
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

2615. Sum of Distances LeetCode Solution in Python

class Solution:
  def distance(self, nums: list[int]) -> list[int]:
    ans = [0] * len(nums)
    numToIndices = collections.defaultdict(list)

    for i, num in enumerate(nums):
      numToIndices[num].append(i)

    for indices in numToIndices.values():
      n = len(indices)
      if n == 1:
        continue
      sumSoFar = sum(indices)
      prevIndex = 0
      for i in range(n):
        sumSoFar += (i - 1) * (indices[i] - prevIndex)
        sumSoFar -= (n - 1 - i) * (indices[i] - prevIndex)
        ans[indices[i]] = sumSoFar
        prevIndex = indices[i]

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents