LeetCode 1685: Sum of Absolute Differences in a Sorted Array Solution

Master LeetCode problem 1685 (Sum of Absolute Differences in a Sorted Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1685. Sum of Absolute Differences in a Sorted Array

Medium

Array Math Prefix Sum

Problem Explanation

Explanation

The key idea to solving this problem is to calculate the absolute differences between each element and all other elements in the array. We can do this efficiently by first calculating the total sum of all differences and then updating the result array accordingly for each element.

Calculate the total sum of absolute differences between all pairs of elements in the array.
Initialize a variable totalSum to store the total sum of absolute differences.
Initialize a variable leftSum to store the sum of absolute differences to the left of the current element.
Initialize a variable rightSum to store the sum of absolute differences to the right of the current element.
Iterate through the array and update the result array based on the calculated sums.

Time Complexity: O(n) where n is the number of elements in the array.

Space Complexity: O(1) excluding the output array.

Solutions

Java

Solution Code

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int totalSum = 0;
        for (int i = 1; i < n; i++) {
            totalSum += nums[i] - nums[0];
        }
        
        int leftSum = 0;
        int rightSum = totalSum;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            result[i] = i * nums[i] - leftSum + rightSum - (n - i) * nums[i];
            if (i < n - 1) {
                leftSum += nums[i];
                rightSum -= nums[i + 1];
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1685 (Sum of Absolute Differences in a Sorted Array)?

This page provides optimized solutions for LeetCode problem 1685 (Sum of Absolute Differences in a Sorted Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1685 (Sum of Absolute Differences in a Sorted Array)?

The time complexity for LeetCode 1685 (Sum of Absolute Differences in a Sorted Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1685 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1685 in Java, C++, or Python.

Back to LeetCode Solutions