2615. Sum of Distances

// 演算法:把相同值的下標分在一組(用 qsort 排序 {值, 下標} 配對後,
// 相同值會自然相鄰)。再對每組用前綴和,讓位置 m 的答案在 O(1) 內算出。
// Algorithm: sort {value, index} pairs so equal values are adjacent, then for
// each value-group sweep once using a running leftSum to get each answer in O(1).

#include <stdlib.h>   // 為了 malloc / calloc / free / qsort / for malloc, calloc, free, qsort

// 把「值 + 原下標」綁成一個型別,方便一起排序 / group value and original index together for sorting
typedef struct {
    int val;   // nums[i] 的數值 / the value
    int idx;   // 它在 nums 中的原始下標 / its original position in nums
} Pair;

// qsort 的比較函式:先按 val,再按 idx(idx 其實本來就遞增,但寫出來更安全)
// Comparator for qsort: order by val, then by idx (indices are already in order,
// but specifying it makes behavior deterministic).
static int cmp(const void *a, const void *b) {
    const Pair *pa = (const Pair*)a;   // 轉回 Pair 指標 / cast void* back to Pair*
    const Pair *pb = (const Pair*)b;
    if (pa->val != pb->val)
        // 不能直接 return pa->val - pb->val(可能溢位);用比較結果 -1/0/1 / avoid subtraction overflow
        return (pa->val > pb->val) - (pa->val < pb->val);
    return (pa->idx > pb->idx) - (pa->idx < pb->idx);
}

// LeetCode 指定的函式簽名:回傳 long long 陣列,並透過 *returnSize 回傳長度
// LeetCode-required signature: returns a heap-allocated long long array and writes length into *returnSize.
long long* distance(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;                                                      // 設定回傳長度 / set output length

    // calloc 會把每個元素初始化為 0,單元素組直接就是正確答案 / calloc zero-fills, which is already
    // correct for groups of size 1 (they never get overwritten).
    long long *ans = (long long*)calloc((size_t)numsSize, sizeof(long long));

    // 為每個下標建立一個 Pair,準備排序 / build one Pair per index, ready to sort
    Pair *arr = (Pair*)malloc(sizeof(Pair) * (size_t)numsSize);
    for (int i = 0; i < numsSize; i++) {
        arr[i].val = nums[i];  // 複製值 / copy the value
        arr[i].idx = i;        // 記住原本位置 / remember the original index
    }

    // 排序後,相同 val 的 Pair 會排在連續區段 / after sorting, equal values form contiguous runs
    qsort(arr, (size_t)numsSize, sizeof(Pair), cmp);

    // 用兩個指標 l、r 掃出每一段「相同值」的區間 [l, r) / sweep contiguous runs of equal values
    int l = 0;
    while (l < numsSize) {
        int r = l;
        // 把 r 推到下一個不同值的位置 / advance r past all equal values
        while (r < numsSize && arr[r].val == arr[l].val) r++;

        int k = r - l;             // 本組的元素個數 / size of this value-group

        // 先算整組下標總和 total / first compute the total of all indices in this group
        long long total = 0;
        for (int i = l; i < r; i++) total += arr[i].idx;

        // leftSum 在掃的過程中累加:目前位置左邊所有下標的和 / running sum of indices already visited
        long long leftSum = 0;
        for (int i = l; i < r; i++) {
            int m = i - l;                      // m 是在組內的位置(從 0 算起)/ position within the group
            long long pm = arr[i].idx;          // 這個元素的原下標 / original index of current element
            // 右邊的總和就是總和扣掉左邊與自己 / right-side sum is what remains after removing leftSum and pm
            long long rightSum = total - leftSum - pm;
            // 左邊貢獻:m 個 (pm - p_j) 加起來 = m*pm - leftSum / left part: m*pm minus indices before me
            long long left  = (long long)m * pm - leftSum;
            // 右邊貢獻:(k-1-m) 個 (p_j - pm) 加起來 = rightSum - (k-1-m)*pm / right part
            long long right = rightSum - (long long)(k - 1 - m) * pm;
            ans[arr[i].idx] = left + right;     // 寫回原本下標的位置 / write to the original slot
            leftSum += pm;                      // 下一輪前把自己併入 leftSum / fold current index into leftSum
        }

        l = r;   // 跳到下一組 / jump to next group
    }

    free(arr);   // 歸還 Pair 陣列的記憶體 / release the Pair buffer
    return ans;  // ans 由呼叫端釋放(LeetCode 的慣例)/ caller frees ans, per LeetCode convention
}

// 演算法:用 unordered_map 把「值 → 該值出現的所有下標」分組,再對每組用
// 前綴和掃一遍,每個位置 O(1) 取得答案。時間與空間皆為 O(n) 平均。
// Algorithm: bucket indices by value with an unordered_map, then sweep each
// bucket once using a running leftSum. Average O(n) time and space.

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    // LeetCode 要求成員函式名為 distance,回傳 vector<long long>
    // LeetCode requires a member function named distance returning vector<long long>.
    vector<long long> distance(vector<int>& nums) {
        int n = (int)nums.size();                // 陣列長度 / problem size
        vector<long long> ans(n, 0);             // 預設 0,單元素組就是正確答案 / defaults cover size-1 groups

        // unordered_map<int, vector<int>>:鍵是 nums 的值,值是它出現過的下標列表
        // Hash map from a value in nums to the list of indices where it appears.
        unordered_map<int, vector<int>> groups;
        groups.reserve(n);                       // 預留桶數,減少重新雜湊 / avoid rehashing as we insert

        // 一次掃過 nums,把下標 i 推到對應值的 vector 尾端 / one pass to bucket indices
        for (int i = 0; i < n; i++) {
            groups[nums[i]].push_back(i);        // 若 key 不存在會自動新建空 vector / default-inserts empty vector
        }

        // Range-for 搭配結構化綁定:直接把 pair<const int, vector<int>> 拆成 (val, idxs)
        // auto& 代表取參考(不拷貝),我們只讀不改,其實用 const auto& 也可以
        // Range-for with structured bindings unpacks each map entry into named vars;
        // auto& avoids copying the vector inside each entry.
        for (auto& [val, idxs] : groups) {
            (void)val;                           // 我們用不到 val 本身,只需要下標列表 / val unused; suppress warning
            int k = (int)idxs.size();            // 本組元素個數 / size of this bucket

            // idxs 內的下標本來就是遞增的(我們按照 i 從 0 到 n-1 推入)
            // Indices inside idxs are already sorted because we pushed i in order.
            long long total = 0;
            for (int x : idxs) total += x;       // 計算整組下標總和 / sum of all indices in this bucket

            long long leftSum = 0;               // 位置 m 左邊所有下標之和 / running sum of earlier indices
            for (int m = 0; m < k; m++) {
                long long pm = idxs[m];                                  // 目前元素的原下標 / current index
                long long rightSum = total - leftSum - pm;               // 右邊之和 = 全部 - 左邊 - 自己 / right sum
                long long left  = (long long)m * pm - leftSum;           // 左邊距離和 / distance sum to the left
                long long right = rightSum - (long long)(k - 1 - m) * pm;// 右邊距離和 / distance sum to the right
                ans[idxs[m]] = left + right;                             // 寫回答案 / write answer to original slot
                leftSum += pm;                                           // 併入 leftSum,給下一個 m 使用 / update rolling sum
            }
        }

        return ans;   // 回傳答案 vector / return the answer vector
    }
};