1685. Sum of Absolute Differences in a Sorted Array

Problem Description

In this problem, we have an array nums that is sorted in non-decreasing order. Our goal is to construct a new array result of the same length as nums. Each element result[i] in this new array should be the sum of the absolute differences between nums[i] and every other element in the array nums. Essentially, for a given element nums[i], we calculate the absolute value of the difference between nums[i] and each element nums[j] where j goes from 0 to the length of the array but is not equal to i. Then we add up all these absolute differences to get result[i].

Intuition

The direct approach would be to calculate the sum of absolute differences for each element in the array by iterating over the array for each element, which would be very inefficient with a time complexity of O(n^2). Instead, we can utilize the fact that the array is sorted and leverage a prefix sum technique that will allow us to calculate the sum of absolute differences in a more efficient manner.

Intuition behind the solution: Since the array is sorted, all numbers to the left of nums[i] are less than or equal to nums[i], and all numbers to the right are greater than or equal to it. So, for nums[i], to get the sum of absolute differences, we can sum the differences between nums[i] and all numbers to its left, and then sum the differences between nums[i] and all numbers to its right.

The key insight here is to realize that we can compute the sum of absolute differences for nums[i] using Cumulative Sum (also known as Prefix Sum). A Cumulative Sum is an array cumsum where cumsum[i] represents the sum of the elements nums[0] up to nums[i]. With this, the sum of differences to the left of nums[i] can be found by nums[i] * i - cumsum[i-1] (since nums[i] is larger than each of these numbers) and the sum of the differences to the right of nums[i] can be found by (cumsum[n-1] - cumsum[i]) - nums[i] * (n-1-i) (since nums[i] is smaller than each of these numbers, subtracting it from the cumulative sum gives us the sum of the differences). By adding these two quantities together, we get the sum of absolute differences for each nums[i].

In the provided solution, instead of keeping a separate array for the cumulative sum, the sum of all elements s and running total of sums t are used to avoid extra space. We iterate through the array, updating t and calculating the sum of absolute differences on the fly.

Learn more about Math and Prefix Sum patterns.

Solution Approach

Understanding the provided Python code requires us to focus on how it implements the prefix sum technique described in the Intuition.

First, let's go through the steps involved in the algorithm:

Initialize an empty list ans, which will be our result array to store the summation of absolute differences for each element.
Compute the total sum s of the array nums. This will be used to calculate the sum of all elements to the right of the current element.
Initialize a variable t to keep track of the cumulative sum (or running total) of the elements as we iterate through the list. This will be used to calculate the sum of all elements to the left of the current element.
Loop through the array nums using enumerate to get both the index i and the value x at each iteration.
For current element x, calculate the sum of absolute differences using the following steps:
- Calculate the sum of differences between x and all the elements on its left (the smaller elements). We can get this by multiplying x with its index i, which gives us the sum of x added i times, and subtracting the running total t which represents the sum of all elements up to x.
- Calculate the sum of differences between x and all the elements on its right (the larger elements). This is done by subtracting the running total t and x itself from the total sum s to get the sum of all elements to the right of x, and then subtracting x multiplied by the number of elements to the right of it (len(nums) - i).
- Add both sums to get the total sum of absolute differences for x and append this value to ans.
Update the running total t by adding the current element value x to it.
After the loop is completed, return ans as the result array.

The step where the absolute difference is calculated, the mathematical formulation is as follows:

v = x * i - t + s - t - x * (len(nums) - i)

This line of the code can be broken down into parts:

x * i: The sum of x added i times.
- t: Subtract the cumulative sum of elements to the left.
+ s - t: Total sum minus the cumulative sum to get sum of all elements to the right.
- x * (len(nums) - i): Subtract x times the count of elements to the right.

Putting the pieces together, this approach efficiently calculates the desired values with a time complexity of O(n), significantly reducing the computational load compared to a naive O(n^2) method of calculating absolute differences for each element individually.

The algorithm cleverly handles the calculation without using additional space for a cumulative sum array by updating and utilizing t for the running total and s as the total sum. By doing this, it's possible to compute the answer in a single pass after calculating the sum of the array just once at the beginning.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach. Suppose our array nums is [1, 3, 6, 10].

Following the solution steps:

We initialize our result array ans as an empty list.
The total sum s of nums is calculated as 1 + 3 + 6 + 10 = 20.
We set t to 0 which will hold the cumulative sum as we iterate.
Now we iterate through nums. Here are the detailed steps:
- First iteration (i=0, x=1):
  - Calculate the left sum: x*i - t which is 1*0 - 0 = 0 because there are no elements to the left of the first element.
  - Calculate the right sum: (s - t) - x*(len(nums)-i) which is (20 - 0) - 1*(4-0) = 20 - 1*4 = 16.
  - The total sum of absolute differences for x is 0 + 16 = 16. So we append 16 to ans.
  Now ans is [16].
  - We update t by adding x to it: t = 0 + 1 = 1.
- Second iteration (i=1, x=3):
  - Left sum: x*i - t which is 3*1 - 1 = 2 since the sum of all elements to the left of 3 is 1.
  - Right sum: (s - t) - x*(len(nums)-i) which is (20 - 1) - 3*(4-1) = 19 - 3*3 = 10.
  - The total sum of differences is 2 + 10 = 12. Append 12 to ans.
  Now our ans is [16, 12].
  - Update t: t = 1 + 3 = 4.
- Third iteration (i=2, x=6):
  - Left sum: x*i - t which is 6*2 - 4 = 8 since the sum of 1 + 3 is 4.
  - Right sum: (s - t) - x*(len(nums)-i) which is (20 - 4) - 6*(4-2) = 16 - 6*2 = 4.
  - The total is 8 + 4 = 12. Append 12 to ans.
  Our ans is now [16, 12, 12].
  - Update t: t = 4 + 6 = 10.
- Fourth iteration (i=3, x=10):
  - Left sum: x*i - t which is 10*3 - 10 = 20 since the sum of 1 + 3 + 6 is 10.
  - Right sum: There are no elements to the right of the last element, hence the value is 0.
  - The total is 20 + 0 = 20. Append 20 to ans.
  Now ans is [16, 12, 12, 20].
  - There's no need to update t as we're at the end of the array.
We've completed the loop and now ans holds our final result, which is [16, 12, 12, 20].

Thus, the array [1, 3, 6, 10] transforms into [16, 12, 12, 20] following our solution approach. Each element in the result array represents the sum of the absolute differences between that element in nums and all other elements. This process provides a much more efficient calculation with a linear time complexity.

Solution Implementation

1from typing import List
2
3class Solution:
4    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
5        # Initialize a list to store the answers.
6        answers = []
7      
8        # Calculate the sum of the entire array to use later in calculations.
9        total_sum = sum(nums)
10      
11        # Initialize a prefix sum to 0.
12        prefix_sum = 0
13      
14        # Iterate through the list, with both the index and the value.
15        for index, value in enumerate(nums):
16            # Compute the value for the current index.
17            # 'value * index' is the sum of 'value' being subtracted from all
18            # elements to the left of 'value' (including itself).
19            # 'total_sum - prefix_sum' is the sum of all the elements to the
20            # right of 'value'.
21            # Subtract 'value * (len(nums) - index)', which is 'value' being
22            # added to all elements to the right of 'value'.
23            current_value = value * index - prefix_sum + total_sum - prefix_sum - value * (len(nums) - index)
24          
25            # Append the computed value to the answer list.
26            answers.append(current_value)
27          
28            # Update the prefix sum with the current value.
29            prefix_sum += value
30      
31        # Return the list of computed answers.
32        return answers
33

1class Solution {
2    public int[] getSumAbsoluteDifferences(int[] nums) {
3        // Initialize the total sum of the array elements to 0
4        int totalSum = 0;
5      
6        // Calculate the total sum of the array elements
7        for (int num : nums) {
8            totalSum += num;
9        }
10
11        int n = nums.length; // Store the length of the array
12        int[] result = new int[n]; // Initialize the result array to store answers
13        int prefixSum = 0; // Initialize the prefix sum to keep track of the sum of elements till the current index
14
15        // Loop through each element to calculate the sum of absolute differences
16        for (int i = 0; i < n; ++i) {
17            // Calculate the sum of absolute difference for the current element
18            // The sum of differences of all elements to the left of the current
19            // element can be found by nums[i] * i (since there are 'i' elements to the left)
20            // minus the sum of all elements to the left which is given by prefixSum (t in your code).
21            // Similarly, the sum of differences of all elements to the right of the current
22            // element is the total sum of all elements minus the sum of all elements till the
23            // current index (including itself), minus the sum total of the elements to the left 
24            // times the number of elements to the right: (totalSum - prefixSum - nums[i]) * (n - i).
25            int sumAbsoluteDifferences = nums[i] * i - prefixSum + totalSum - prefixSum - nums[i] * (n - i);
26            result[i] = sumAbsoluteDifferences; // Assign the computed value to the result array
27            prefixSum += nums[i]; // Update the prefix sum with the current element's value
28        }
29
30        // Return the final result array
31        return result;
32    }
33}
34

1#include <vector>
2#include <numeric> // For std::accumulate
3
4class Solution {
5public:
6    // Function to calculate the sum of absolute differences of each element
7    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
8        // Calculate the sum of the entire array
9        int total_sum = std::accumulate(nums.begin(), nums.end(), 0);
10        // Initialize variable to keep track of the sum of elements seen so far
11        int partial_sum = 0;
12        // Get number of elements in the array
13        int n = nums.size();
14        // Initialize result vector with the same size as input
15        vector<int> result(n);
16      
17        // Iterate over each element in the array
18        for (int i = 0; i < n; ++i) {
19            // Calculate the sum of absolute differences for the current element
20            int absolute_difference_sum = nums[i] * i - partial_sum 
21                                          + total_sum - partial_sum 
22                                          - nums[i] * (n - i);
23            // Store the result in the corresponding position
24            result[i] = absolute_difference_sum;
25            // Update the partial sum with the value of the current element
26            partial_sum += nums[i];
27        }
28        // Return the final result vector
29        return result;
30    }
31};
32

1function getSumAbsoluteDifferences(nums: number[]): number[] {
2    // Calculate the sum of all elements in the array.
3    const totalSum = nums.reduce((previousValue, currentValue) => previousValue + currentValue, 0);
4    let cumulativeSum = 0;
5    const length = nums.length;
6    const result = new Array(length); // Initialize the result array.
7
8    // Iterate through the elements of the array to calculate the
9    // sum of absolute differences for each element.
10    for (let i = 0; i < length; ++i) {
11        // Calculate the sum of absolute differences for nums[i]:
12        // This includes the difference between nums[i] and each element to the left of it,
13        // and each element to the right of it.
14        const absoluteDifferenceSum = nums[i] * i - cumulativeSum
15                                      + totalSum - cumulativeSum - nums[i] * (length - i);
16        result[i] = absoluteDifferenceSum; // Store the computed value in the result array.
17      
18        // Update the cumulative sum with the value of the current element.
19        cumulativeSum += nums[i];
20    }
21    return result; // Return the final array containing the sum of absolute differences for each element.
22}
23

Time and Space Complexity

The given code snippet implements an algorithm to get the sum of absolute differences for each number in the input list nums with every other number in the list.

Time Complexity:

To analyze the time complexity, let's consider the number of operations performed by the code:

We first calculate the sum of all numbers in nums (s = sum(nums)). This iteration over the array has a time complexity of O(n), where n is the number of elements in nums.
Then, we iterate over the list nums once. For each element x at index i, we calculate the sum of absolute differences using the precomputed total sum s and the temporary sum t. The formula v = x * i - t + s - t - x * (len(nums) - i) does so using a constant number of operations for each element.
The total number of operations inside the loop is independent of the size of the list, meaning it's O(1) per element.
As we do a constant amount of work for each of the n elements during this iteration, the time complexity for this loop is O(n).

Combining both steps, the overall time complexity of the algorithm is O(n) + O(n), which simplifies to O(n).

Space Complexity:

When analyzing the space complexity of the code, consider the following:

A new list ans is created to store the result. In the worst case, it will contain the same number of elements as the input list nums, hence it takes O(n) space.
The variables s, t, and v use constant space, i.e., O(1).
Since all other variables (i and x) are also using constant space and there are no other data structures used, the total additional space used by the algorithm is essentially the space taken by the ans list.

Therefore, the overall space complexity of the function is O(n).

In summary, the function has a time complexity of O(n) and a space complexity of O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know