Sum of Absolute Differences in a Sorted Array | TRICKY | OA LEVEL | MUST DO

https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/

You are given an integer array nums sorted in non-decreasing order.
Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.
In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Example 1:
Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.

Example 2:
Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]


----------------------------------------------------------------------------------------------------------------------
Example :- nums = [1,4,6,8,10]

I will ignore same number subtractions like |x-x|, cuz that is zero anyways. Our goal is to get a positive difference out of every subtraction.

For index i=0,
res[i]=(4-1)+(6-1)+(8-1)+(10-1) = 1*(-4) + (4+6+8+10) => 1 * (0 - 4) + (0 + 4+6+8+10)

For index i=1,
res[i]=(4-1)+(6-4)+(8-4)+(10-4) = 4*(-2) + (-1+6+8+10) => 4 * (1 - 3) + (-1 + 6+8+10)

For index i=2,
res[i]=(6-1)+(6-4)+(8-6)+(10-6) = 6*(0) + (-1-4+8+10) => 6 * (2 - 2) + (-1-4 + 8+10)

For index i=3,
res[i]=(8-1)+(8-4)+(8-6)+(10-8) = 8*(2) + (-1-4-6+10) => 8 * (3 - 1) + (-1-4-6 + 10)

For index i=4,
res[i]=(10-1)+(10-4)+(10-6)+(10-8) = 10*(4) + (-1-4-6-8) => 10 * (4 - 0) + (-1-4-6-8 + 0)

We can clearly observe the pattern,

res[i]=nums[i] * (Elements on left of i - Elements on right of i) +
                 (Sum of elements on right of i - Sum of elements on left of i)

-----------------------------------------------------------------------------------------------------------------------
class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n=nums.size();

        vector<int> prefix=nums;
        for(int i=1;i<n;i++){
            prefix[i]+=prefix[i-1];
        }

        vector<int> res(n);

        for(int i=0;i<n;i++){
            int L=i>0 ? prefix[i-1] : 0;
            int R=prefix[n-1]-prefix[i];

            int countL=i;
            int countR=n-1-i;
            int cnt=countL-countR;

            res[i]=nums[i]*cnt+(R-L);
        }
        return res;
    }
};