1685. Sum of Absolute Differences in a Sorted Array (LeetCode) (solution: C++, C#)

 

Problem Name: 1685. Sum of Absolute Differences in a Sorted Array

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

Difficulty: Medium

Tag: Array | Math | Prefix Sum

Language: C# | C++

OJ: LeetCode

Algorithm:

1. Initialize three arrays: result, previous, and next.

2. Compute previous by accumulating forward absolute differences.

3. Compute next by accumulating backward absolute differences.

4. For each element, combine corresponding previous and next values.

5. Return the result array.

Code(C#)

public class Solution
{
    public int[] GetSumAbsoluteDifferences(int[] nums)
    {
        int[] result = new int[nums.Length];
        int[] previous = new int[nums.Length];
        int[] next = new int[nums.Length];
        int value = nums.Length;
        previous[0] = 0;
        for(int i=1; i<nums.Length; i++)
            previous[i] = previous[i-1] + (i * (nums[i]-nums[i - 1]));
        next[value - 1] = 0;
        for (int i = value-2, j=1; i >= 0; i--,j++)
            next[i] = next[i+1] + (j * (nums[i+1] - nums[i]));
        for (int i=0; i<nums.Length; i++,value--)
        {
            Console.WriteLine($"{previous[i]} {next[i]}");
            result[i] = previous[i] +next[i];
        }
        return result;
    }
}

Code(C++)

class Solution {

public:

    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {

        int n = nums.size();

        vector<int> result(n);

        vector<int> previous(n);

        vector<int> next(n);

        previous[0] = 0;

        for (int i = 1; i < n; ++i)

            previous[i] = previous[i - 1] + i * (nums[i] - nums[i - 1]);

        next[n - 1] = 0;

        for (int i = n - 2, j = 1; i >= 0; --i, ++j)

            next[i] = next[i + 1] + j * (nums[i + 1] - nums[i]);

        for (int i = 0; i < n; ++i)

            result[i] = previous[i] + next[i];

        return result;

    }

};