Sponsored
Sponsored
The naive approach involves calculating the summation of absolute differences directly for each element. For each element `nums[i]` in the array, iterate through every other element `nums[j]` and accumulate the absolute difference `|nums[i] - nums[j]|`. This results in a straightforward solution but with a time complexity of O(n^2) due to the nested loops.
Time Complexity: O(n^2) where n is the length of the array.
Space Complexity: O(n) for the result array.
1function getSumAbsoluteDifferences(nums) {
2 let result = [];
3 for (let i = 0; i < nums.length; i++) {
4 let sum = 0;
5 for (let j = 0; j < nums.length; j++) {
6 sum += Math.abs(nums[i] - nums[j]);
7 }
8 result.push(sum);
9 }
10 return result;
11}
12
13let nums = [2, 3, 5];
14console.log(getSumAbsoluteDifferences(nums));
15This JavaScript solution uses two nested loops to calculate the sum of absolute differences. Each result is appended to a result array, which is returned and logged to the console.
To optimize the solution, use prefix sums to reduce redundant calculations. Compute prefix sums `leftSum` and `rightSum` to capture cumulative totals on each side of the current index. For each nums[i], compute the contribution using:
i, each number nums[j] contributes to |nums[i] - nums[j]| as nums[i] - nums[j].i to end, each number nums[j] contributes as nums[j] - nums[i].Time Complexity: O(n) as each element is processed only twice.
Space Complexity: O(n) to store the result.
This C implementation uses cumulative `leftSum` and `rightSum` to keep track of elements processed. By adjusting these sums and using the formula, we efficiently calculate the results in O(n) time.