2615. Sum of Distances

/**
 * Problem: LeetCode 2615 - Sum of Distances
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public long[] distance(int[] nums) {
        final int n = nums.length;
        long[] result = new long[n];
        
        // Group 0-indexed positions for each unique value
        Map<Integer, List<Integer>> posMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            posMap.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        
        for (List<Integer> indices : posMap.values()) {
            final int m = indices.size();
            if (m <= 1) continue;
            
            long totalSum = 0;
            for (int idx : indices) {
                totalSum += idx;
            }
            
            long leftSum = 0;
            for (int k = 0; k < m; k++) {
                long currentIdx = indices.get(k);
                long rightSum = totalSum - leftSum - currentIdx;
                
                long leftContribution = (long) k * currentIdx - leftSum;
                long rightContribution = rightSum - (long) (m - 1 - k) * currentIdx;
                
                result[(int) currentIdx] = leftContribution + rightContribution;
                leftSum += currentIdx;
            }
        }
        
        return result;
    }
}

"""
Problem: LeetCode 2615 - Sum of Distances
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List
from collections import defaultdict


class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n

        pos_map = defaultdict(list)
        for i, val in enumerate(nums):
            pos_map[val].append(i)

        for indices in pos_map.values():
            m = len(indices)
            if m <= 1:
                continue

            total_sum = sum(indices)
            left_sum = 0

            for k, idx in enumerate(indices):
                right_sum = total_sum - left_sum - idx
                left_contrib = k * idx - left_sum
                right_contrib = right_sum - (m - 1 - k) * idx
                result[idx] = left_contrib + right_contrib
                left_sum += idx

        return result

/**
 * Problem: LeetCode 2615 - Sum of Distances
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        int n = nums.size();
        vector<long long> result(n, 0);
        
        unordered_map<int, vector<int>> posMap;
        for (int i = 0; i < n; ++i) {
            posMap[nums[i]].push_back(i);
        }
        
        for (const auto& [val, indices] : posMap) {
            int m = indices.size();
            if (m <= 1) continue;
            
            long long totalSum = 0;
            for (int idx : indices) {
                totalSum += idx;
            }
            
            long long leftSum = 0;
            for (int k = 0; k < m; ++k) {
                long long currentIdx = indices[k];
                long long rightSum = totalSum - leftSum - currentIdx;
                
                long long leftContrib = (long long) k * currentIdx - leftSum;
                long long rightContrib = rightSum - (long long) (m - 1 - k) * currentIdx;
                
                result[currentIdx] = leftContrib + rightContrib;
                leftSum += currentIdx;
            }
        }
        
        return result;
    }
};

/**
 * Problem: LeetCode 2615 - Sum of Distances
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var distance = function(nums) {
    const n = nums.length;
    const result = new Array(n).fill(0);

    const posMap = new Map();
    for (let i = 0; i < n; i++) {
        const val = nums[i];
        let list = posMap.get(val);
        if (!list) {
            list = [];
            posMap.set(val, list);
        }
        list.push(i);
    }

    for (const indices of posMap.values()) {
        const m = indices.length;
        if (m <= 1) continue;

        let totalSum = 0;
        for (let i = 0; i < m; i++) {
            totalSum += indices[i];
        }

        let leftSum = 0;
        for (let k = 0; k < m; k++) {
            const currentIdx = indices[k];
            const rightSum = totalSum - leftSum - currentIdx;

            const leftContrib = k * currentIdx - leftSum;
            const rightContrib = rightSum - (m - 1 - k) * currentIdx;

            result[currentIdx] = leftContrib + rightContrib;
            leftSum += currentIdx;
        }
    }

    return result;
};