<p>You are given an integer array <code>nums</code> sorted in <strong>non-decreasing</strong> order.</p>

<p>Build and return <em>an integer array </em><code>result</code><em> with the same length as </em><code>nums</code><em> such that </em><code>result[i]</code><em> is equal to the <strong>summation of absolute differences</strong> between </em><code>nums[i]</code><em> and all the other elements in the array.</em></p>

<p>In other words, <code>result[i]</code> is equal to <code>sum(|nums[i]-nums[j]|)</code> where <code>0 &lt;= j &lt; nums.length</code> and <code>j != i</code> (<strong>0-indexed</strong>).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,5]
<strong>Output:</strong> [4,3,5]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,4,6,8,10]
<strong>Output:</strong> [24,15,13,15,21]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= nums[i + 1] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        # Approach 1
        # 2, 3, 5
        # a, b, c
        # |a - b| + |a - c|, |b - a| + |b - c|, |c - a| + |c - b|
        # x = |a - b|, y = |a - c|, z = |b - c|
        #   a b c
        # a 0 x y - x + y
        # b x 0 z - x + z
        # c y z 0 - y + z
        # Approach 2
        # a, b, c | a < b < c
        # a: c - a, b - c
        # b: d - b, c - b, b - a
        # c: d - c, c - b, c - a
        # d: d - c, d - b, d - a
        # (b - a) + (c - a), (b - a) + (c - b), (c - a) + (c - b)
        # b + c - 2a, c - a, 2c - a - b
        # s - 3a, s - 2a - b, s - 2a - 2b + c
        # prefix sum
        # a  i   j   k   l
        # a a+b i+c j+d k+e
        # a - b + a - c + a - d + a - e | 4a - (b + c + d + e) | 4a - r
        # a - b + b - c + b - d + b - e | (a + b) + b - (c + d + e) | i + b - q
        # a - c + b - c + c - d + c - e | (a + b + c) - c - (d + e) | j - c - p
        # a - d + b - d + c - d + d - e | (a + b + c + d) - 4d - e | k - 4d - e
        # a+r b+q c+p d+e e
        #  s   r   q   p  e
        # a - e + b - e + c - e + d - e = s - 4e
        # a - d + 
        # i       0  1  2  3  4  5
        # nums    1  4  6  8  10
        # prefix  0  1  5  11 19 29
        # suffix  29 28 24 18 10 0
        # ans     24 15 13 15 21
        # 
        n = len(nums)
        diffs = []
        prefixSum = [0] * (n + 1)
        suffixSum = [0] * (n + 1)
        ans = [0] * n
        for i in range(1, n + 1):
            prefixSum[i] = prefixSum[i-1] + nums[i-1]

        for i in range(n-1, 0, -1):
            suffixSum[i] = suffixSum[i+1] + nums[i]

        for i in range(n):
            ans[i] = i * nums[i] - prefixSum[i] + suffixSum[i+1] - (n-1-i) * nums[i]

        return ans
        
        # for i in range(n):
        #     diffs.append([0] * n)

        # for i in range(n):
        #     for j in range(i):
        #         diffs[i][j] = diffs[j][i]

        #     for j in range(i+1, n):
        #         diffs[i][j] = abs(nums[i] - nums[j])

        #     ans[i] = sum(diffs[i][:])
        # return ans

626