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.
1using System;
2
3class Program {
4 static int[] GetSumAbsoluteDifferences(int[] nums) {
5 int n = nums.Length;
6 int[] result = new int[n];
7 for (int i = 0; i < n; i++) {
8 int sum = 0;
9 for (int j = 0; j < n; j++) {
10 sum += Math.Abs(nums[i] - nums[j]);
11 }
12 result[i] = sum;
13 }
14 return result;
15 }
16
17 static void Main() {
18 int[] nums = { 2, 3, 5 };
19 int[] result = GetSumAbsoluteDifferences(nums);
20 Console.WriteLine(string.Join(" ", result));
21 }
22}
23C# implementation uses nested loops to compute the sum of absolute differences across all elements in the array. The results are stored and printed using string.Join.
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.