1685. Sum of Absolute Differences in a Sorted Array

📝 Problem Details

• Title: 1685. Sum of Absolute Difference in a Sorted Array
• Link: https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/
• Difficulty: Medium
• Tags/Categories: Math Prefix-Sum Arrays

💭What Were My Initial Thoughts?

- brute force would be to calculate the cumulative sum over n^2 iterations
- interviewer pointed out that there is potentially a pattern in our caclulations that could help
- if we first calculate the sum of all elements, we can use a formula to do the absolute difference calculations in linear time 
- the input array is sorted in non-decreasing order

🤔What Did I Struggle With?

~ my formula was wrong in the interview, was short on time 

💡 Explanation of Solution

- precompute the total sum of the array
- divide and conquer : for each nums[i], split the array into two parts:
	- left part: sumLeft = the concatenation of nums[i] elements
	- right part: sumRight = totalSum - sumLeft - nums[i]
	- using sumLeft and sumRight, compute the sum of absolute differences
	- result[i] = i * nums[i] - sumLeft + sumRight - (n - i - 1) * nums[i]

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n) for the use of the results vector 

💻 Implementation of Solution

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        vector<int> result(n,0);
        int sumLeft = 0;
        int sumRight = 0;
 
        for(int i=0; i < n; i++) {
            sumRight = totalSum - sumLeft - nums[i];
            result[i] = i * nums[i] - sumLeft + sumRight - (n - i - 1) * nums[i];
            sumLeft += nums[i];
        }
 
        return result;
    }
};