Leetcode 1685: Sum of Absolute Differences in a Sorted Array

Input: The input consists of a sorted integer array `nums`.

Example: nums = [2, 3, 5]

Constraints:

• 2 <= nums.length <= 10^5

• 1 <= nums[i] <= nums[i + 1] <= 10^4

Output: Return an integer array `result` where `result[i]` is the summation of the absolute differences between `nums[i]` and all the other elements in `nums`.

Example: Output: [4, 3, 5]

Constraints:

Goal: The goal is to calculate the summation of absolute differences for each element of the array `nums`.

Steps:

• Start by calculating the absolute differences for the first element and store it.

• Then, use an iterative approach to build the result array, where each element `i` is calculated using the differences from the previous element and its neighbors.

Goal: The array `nums` must satisfy the following constraints:

Steps:

• 2 <= nums.length <= 10^5

• 1 <= nums[i] <= nums[i + 1] <= 10^4

Assumptions:

• The array `nums` is already sorted in non-decreasing order.

• Input: Input: nums = [2, 4, 6]

• Explanation: The result for each element is the sum of absolute differences between the element and all other elements in the array.

Approach: To solve this problem, we need to compute the absolute differences efficiently. Since the array is sorted, we can make use of this property to minimize redundant calculations.

Observations:

• The array is sorted, which means we can calculate the differences incrementally.

• We can calculate the result iteratively by adjusting the previous result for the current element rather than recalculating the entire sum each time.

Steps:

• Calculate the total absolute difference for the first element and store it in the result array.

• For each subsequent element, adjust the previous result by adding or subtracting the differences with the adjacent elements, as the array is sorted.

Empty Inputs:

• The input array `nums` should not be empty, as the problem defines that the array length is at least 2.

Large Inputs:

• For large arrays (up to 10^5 elements), the solution needs to be efficient.

Special Values:

• All elements in the array are the same, the result will be an array of zeros since there are no differences.

Constraints:

• Ensure that the solution works within the time limits for the largest input size.

vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
    int z = 0, n = nums.size();
    for(int i = 0; i < n; i++)
        z += nums[i] - nums[0];
    vector<int> ans(n, 0);
    ans[0] = z;
    for(int i = 1; i < n; i++)
        ans[i] = ans[i-1] + i * (nums[i] - nums[i-1]) - (n - i)* (nums[i] - nums[i-1]);
    
    return ans;
}

1 : Function Definition

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

Define the function 'getSumAbsoluteDifferences' which takes a vector of integers 'nums' and returns a vector of integers containing the sum of absolute differences.

2 : Variable Initialization

    int z = 0, n = nums.size();

Initialize the variable 'z' to 0 to accumulate the sum of differences, and 'n' to store the size of the 'nums' vector.

3 : Loop Through Array

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

Start a loop to iterate through each element in the 'nums' array.

4 : Sum Absolute Differences

        z += nums[i] - nums[0];

In each iteration, accumulate the difference between the current element and the first element of the 'nums' array to 'z'.

5 : Array Initialization

    vector<int> ans(n, 0);

Initialize a vector 'ans' of size 'n' with all elements set to 0. This will store the final results.

6 : Set First Element of Result

    ans[0] = z;

Set the first element of the 'ans' vector to 'z', which is the sum of absolute differences calculated for the first element.

7 : Loop Through Remaining Elements

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

Start a loop to process each element in the 'nums' array starting from the second element.

8 : Calculate Differences for Each Element

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

Calculate the sum of absolute differences for the current element by adjusting the previous result. This step uses the previously calculated value to efficiently compute the next result.

9 : Return Statement

    return ans;

Return the vector 'ans' containing the sum of absolute differences for each element.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) as we process each element in the array only once.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) as we store the result array.

Leetcode 1685: Sum of Absolute Differences in a Sorted Array

Explore →