Sum of Absolute Differences in a Sorted Array
Problem Description
You are given an integer array nums sorted in non-decreasing order.
Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.
In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).
Examples:
Input: nums = [3,8,10]
Output: [12,7,9]
Explanation: Assuming the arrays are 0-indexed, then:
result[0] = |3-3| + |3-8| + |3-10| = 0 + 5 + 7 = 12,
result[1] = |8-3| + |8-8| + |8-10| = 5 + 0 + 2 = 7,
result[2] = |10-3| + |10-8| + |10-10| = 7 + 2 + 0 = 9.
Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]
Explanation: For the input nums = [1, 4, 6, 8, 10],
result[0] = |1-1| + |1-4| + |1-6| + |1-8| + |1-10| = 0 + 3 + 5 + 7 + 9 = 24
result[1] = |4-1| + |4-4| + |4-6| + |4-8| + |4-10| = 3 + 0 + 2 + 4 + 6 = 15
result[2] = |6-1| + |6-4| + |6-6| + |6-8| + |6-10| = 5 + 2 + 0 + 2 + 4 = 13
result[3] = |8-1| + |8-4| + |8-6| + |8-8| + |8-10| = 7 + 4 + 2 + 0 + 2 = 15
result[4] = |10-1| + |10-4| + |10-6| + |10-8| + |10-10| = 9 + 6 + 4 + 2 + 0 = 21
Constraints:
- 2 <= nums.length <= 10⁵
- 1 <= nums[i] <= nums[i + 1] <= 10⁴
Brute Force Approach
Okay, so here's the thought process:
For an element in the array, calculate its absolute difference with every other element in the array and sum up these differences.
To achieve this, loop through the array and pick an element. Then, in another nested loop, calculate the absolute difference between the chosen element and every other element.
Store this sum in a result array. Repeat this process for every element in the array, resulting in the final output.
Let's walk through an example:
Let’s perform a dry run for nums = [2, 3, 5]:
Step 1: Initialize result = []
For nums[0] = 2:
- |2 - 3| + |2 - 5| = 1 + 3 = 4
- Append 4 to result.
For nums[1] = 3:
- |3 - 2| + |3 - 5| = 1 + 2 = 3
- Append 3 to result.
For nums[2] = 5:
- |5 - 2| + |5 - 3| = 3 + 2 = 5
- Append 5 to result.
Final result = [4, 3, 5]
How to implement it in code:
- Initialize result array: Create an empty list, result, to store the summations for each element.
- Outer loop: Loop through each element in the array nums (using index i).
- Inner loop: For the current element nums[i], loop through the entire array again (using index j) to calculate the absolute differences |nums[i] - nums[j]| for all j != i.
- Sum and store: Add these differences to get the sum for nums[i], and append it to the result array.
- Return the result: After both loops, return the result array.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
// Get the size of the array
int n = nums.size();
// Initialize the result array with size n and values 0
vector<int> result(n, 0);
// Outer loop: Iterate through each element in nums
for (int i = 0; i < n; i++) {
// Initialize sum for nums[i]
int sum = 0;
// Inner loop: Calculate absolute differences
for (int j = 0; j < n; j++) {
// Add absolute difference to sum
sum += abs(nums[i] - nums[j]);
}
// Store the sum in the result array
result[i] = sum;
}
// Return the result array
return result;
}
};2. Java Try on Compiler
class Solution {
public int[] getSumAbsoluteDifferences(int[] nums) {
// Get the size of the array
int n = nums.length;
// Initialize the result array with size n
int[] result = new int[n];
// Outer loop: Iterate through each element in nums
for (int i = 0; i < n; i++) {
// Initialize sum for nums[i]
int sum = 0;
// Inner loop: Calculate absolute differences
for (int j = 0; j < n; j++) {
// Add absolute difference to sum
sum += Math.abs(nums[i] - nums[j]);
}
// Store the sum in the result array
result[i] = sum;
}
// Return the result array
return result;
}
}
3. Python Try on Compiler
class Solution:
def getSumAbsoluteDifferences(self, nums):
# Get the size of the array
n = len(nums)
# Initialize the result array with size n
result = [0] * n
# Outer loop: Iterate through each element in nums
for i in range(n):
# Initialize sum for nums[i]
sum_val = 0
# Inner loop: Calculate absolute differences
for j in range(n):
# Add absolute difference to sum
sum_val += abs(nums[i] - nums[j])
# Store the sum in the result array
result[i] = sum_val
# Return the result array
return result
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @return {number[]}
*/
var getSumAbsoluteDifferences = function(nums) {
// Get the size of the array
const n = nums.length;
// Initialize the result array with size n
const result = new Array(n).fill(0);
// Outer loop: Iterate through each element in nums
for (let i = 0; i < n; i++) {
// Initialize sum for nums[i]
let sum = 0;
// Inner loop: Calculate absolute differences
for (let j = 0; j < n; j++) {
// Add absolute difference to sum
sum += Math.abs(nums[i] - nums[j]);
}
// Store the sum in the result array
result[i] = sum;
}
// Return the result array
return result;
};
Time Complexity: O(n²)
The time complexity of the brute force solution is O(n²), where n is the length of the array nums.
- The outer loop iterates over each element in the array, running n times.
- For each iteration of the outer loop, the inner loop also iterates over the entire array, performing n operations.
- This results in n + n + n... + n iterations, which is equivalent to n × n.
Thus, the total number of iterations is n × n = O(n²).
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
In this case, the only extra space used is the result array of size n to store the output.
Hence, the auxiliary space complexity is O(n) because the result array is the only additional space used.
Total Space Complexity: O(n)
The input array nums already exists, and its size is n.
Thus, the total space complexity is O(n) because both the input array and the result array together consume O(n) space.
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the size of the array is at most 10⁵, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes! There is a better approach to solve this problem.
Curious?
In our previous approach, we checked for every element's absolute difference with every other element in the array, which resulted in O(n²) time complexity and was inefficient, leading to TLE.
However, we can optimize this.
Since the array is sorted in non-decreasing order, we can leverage the fact that elements to the left of an index are always smaller than or equal to the element at that index, and elements to the right are always greater than or equal to it.
This allows us to simplify the calculation of the absolute differences.
For each element nums[i], the sum of absolute differences can be broken down into two parts:
- The difference between nums[i] and all the elements to the left of it (indices 0 to i-1).
- The difference between nums[i] and all the elements to the right of it (indices i+1 to n-1).
Thus, the total sum for nums[i] is:
- (nums[i] - nums[0]) + (nums[i] - nums[1]) + ... + (nums[i] - nums[i-1]) + (nums[i+1] - nums[i]) + ... + (nums[n-1] - nums[i])
This simplifies to:
- nums[i] * (i+1) - (sum of nums[0] to nums[i]) + (sum of nums[i+1] to nums[n-1]) - nums[i] * (n-i-1)
Now, to efficiently calculate the sums:
- We can precompute the sum of elements from 0 to i and from i+1 to n-1.
- For any index i, the sum from 0 to i is stored and for the sum from i+1 to n-1, we can compute it as the total sum of the array minus the sum from 0 to i.
In simple terms:
- We can create a prefix sum array to store the cumulative sum of elements from the start of the array up to each index.
This way, prefix[i] will store the sum of elements from nums[0] to nums[i].
i.e. prefix[i] = sum of elements from nums[0] to nums[i] - To calculate the sum of elements from index i+1 to n-1, we can simply subtract prefix[i] from the total sum of the array, which is stored as prefix[n-1] (the sum of all elements in the array).
In other words, to get the sum of elements from i+1 to n-1, use:
sum(i+1 to n-1) = prefix[n-1] - prefix[i].
This approach significantly reduces the complexity, making it more efficient than the brute force method.
Let's understand with an example:
Here's a dry run for nums = [1, 4, 6, 8, 10]:
Step 1: Compute the Prefix Sum
- prefix = [1, 5, 11, 19, 29]
- prefix[0] = 1
- prefix[1] = 1 + 4 = 5
- prefix[2] = 5 + 6 = 11
- prefix[3] = 11 + 8 = 19
- prefix[4] = 19 + 10 = 29
Step 2: Compute Total Sum
- total_sum = prefix[4] = 29
Step 3: Calculate Result for Each ElementFor nums[0] = 1:
- Left sum: prefix[0] = 1
- Right sum: total_sum - prefix[0] = 29 - 1 = 28
- Result[0] = 1 * (0 + 1) - 1 + 28 - 1 * (5 - 1) = 1 - 1 + 28 - 4 = 24
For nums[1] = 4:
- Left sum: prefix[1] = 5
- Right sum: total_sum - prefix[1] = 29 - 5 = 24
- Result[1] = 4 * (1 + 1) - 5 + 24 - 4 * (5 - 2) = 8 - 5 + 24 - 12 = 15
For nums[2] = 6:
- Left sum: prefix[2] = 11
- Right sum: total_sum - prefix[2] = 29 - 11 = 18
- Result[2] = 6 * (2 + 1) - 11 + 18 - 6 * (5 - 3) = 18 - 11 + 18 - 12 = 13
For nums[3] = 8:
- Left sum: prefix[3] = 19
- Right sum: total_sum - prefix[3] = 29 - 19 = 10
- Result[3] = 8 * (3 + 1) - 19 + 10 - 8 * (5 - 4) = 32 - 19 + 10 - 8 = 15
For nums[4] = 10:
- Left sum: prefix[4] = 29
- Right sum: total_sum - prefix[4] = 29 - 29 = 0
- Result[4] = 10 * (4 + 1) - 29 + 0 - 10 * (5 - 5) = 50 - 29 + 0 = 21
Step 4: Final Result
- result = [24, 15, 13, 15, 21]
How to code it up?
- Create a prefix sum array where each element prefix[i] stores the sum of elements from nums[0] to nums[i].
- The total sum of the array can be obtained from prefix[n-1], where n is the length of the array.
- For each element nums[i]:
- Compute the sum of differences from elements on the left using prefix[i].
- Compute the sum of differences from elements on the right using prefix[n-1] - prefix[i].
- For each element nums[i], the result is:
result[i] = nums[i]×(i+1) − prefix[i] + (prefix[n−1]−prefix[i])−nums[i] × (n−i−1) - After calculating the result for each index, return the final result array.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
// Get the size of the array
int n = nums.size();
// Initialize the prefix sum array
vector<int> prefix(n, 0);
// Initialize the result array to store the final sums
vector<int> result(n, 0);
// Variable to store the total sum of elements as we build the prefix array
int total_Sum = 0;
for(int i = 0; i < n; i++) {
// Accumulate the sum of elements up to index i
total_Sum += nums[i];
// Store the accumulated sum in the prefix array
prefix[i] = total_Sum;
}
// Now calculate the result for each element
for(int i = 0; i < n; i++) {
// The formula for result[i] based on the simplified equation:
result[i] = (nums[i]*(i+1) - prefix[i] + (prefix[n-1] - prefix[i]) - nums[i]*(n-i-1));
}
// Return the result array containing the sum of absolute differences
return result;
}
};
2. Java Try on Compiler
class Solution {
public int[] getSumAbsoluteDifferences(int[] nums) {
// Get the size of the array
int n = nums.length;
// Initialize the prefix sum array
int[] prefix = new int[n];
// Initialize the result array to store the final sums
int[] result = new int[n];
// Variable to store the total sum of elements as we build the prefix array
int total_Sum = 0;
for (int i = 0; i < n; i++) {
// Accumulate the sum of elements up to index i
total_Sum += nums[i];
// Store the accumulated sum in the prefix array
prefix[i] = total_Sum;
}
// Now calculate the result for each element
for (int i = 0; i < n; i++) {
// The formula for result[i] based on the simplified equation:
result[i] = (nums[i] * (i + 1) - prefix[i] + (prefix[n - 1] - prefix[i]) - nums[i] * (n - i - 1));
}
// Return the result array containing the sum of absolute differences
return result;
}
}
3. Python Try on Compiler
class Solution:
def getSumAbsoluteDifferences(self, nums):
# Get the size of the array
n = len(nums)
# Initialize the prefix sum array
prefix = [0] * n
# Initialize the result array to store the final sums
result = [0] * n
# Variable to store the total sum of elements as we build the prefix array
total_sum = 0
for i in range(n):
# Accumulate the sum of elements up to index i
total_sum += nums[i]
# Store the accumulated sum in the prefix array
prefix[i] = total_sum
# Now calculate the result for each element
for i in range(n):
# The formula for result[i] based on the simplified equation:
result[i] = (nums[i] * (i + 1) - prefix[i] + (prefix[n - 1] - prefix[i]) - nums[i] * (n - i - 1))
# Return the result array containing the sum of absolute differences
return result
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @return {number[]}
*/
var getSumAbsoluteDifferences = function(nums) {
// Get the size of the array
let n = nums.length;
// Initialize the prefix sum array
let prefix = new Array(n).fill(0);
// Initialize the result array to store the final sums
let result = new Array(n).fill(0);
// Variable to store the total sum of elements as we build the prefix array
let totalSum = 0;
for (let i = 0; i < n; i++) {
// Accumulate the sum of elements up to index i
totalSum += nums[i];
// Store the accumulated sum in the prefix array
prefix[i] = totalSum;
}
// Now calculate the result for each element
for (let i = 0; i < n; i++) {
// The formula for result[i] based on the simplified equation:
result[i] = (nums[i] * (i + 1) - prefix[i] + (prefix[n - 1] - prefix[i]) - nums[i] * (n - i - 1));
}
// Return the result array containing the sum of absolute differences
return result;
}Time Complexity: O(n)
The time complexity for this approach is O(n), where n is the length of the array.
- The first loop that calculates the prefix array runs through all n elements once. The complexity is O(n).
- The second loop that calculates the result for each element also iterates over n elements, and the operation it performs is of constant time, so it is O(n) as well.
Therefore, the total time complexity is the sum of the two loops:O(n) + O(n) = O(n).
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
The auxiliary space complexity is O(n) because we use two additional arrays (prefix and result), each of size n. - Total Space Complexity: O(n)
The input array nums already exists, and its size is n..
Thus, the total space complexity is O(n) because of the input array, prefix array and the result array together consume O(n) space.
Follow Up: Can you solve it without prefix array?
Yes, we can solve this without using a prefix array by continuously updating the prefix sum in a variable as we process each element. First, calculate the total sum of the array to determine the right-side contribution. Then, use a prefix_sum variable to track the left-side contribution, updating it after processing each element.
Here’s the approach:
First, calculate the total sum of the array (total_sum). This will help us compute the right-side contribution for each index.
- Use a variable prefix_sum to maintain the sum of elements processed so far. This gives the left-side contribution.
- For each index, calculate the result using:
- The left part: nums[i] * (i + 1) - prefix_sum (sum of differences for elements on the left).
- The right part: (total_sum - prefix_sum) - nums[i] * (n - i - 1) (sum of differences for elements on the right).
- Update prefix_sum as you process each element, and store the result for every index.