Sponsored
Sponsored
The idea is to use prefix sums to efficiently calculate the sum of elements up to any index and from any index to the end.
First, compute the prefix sum of the array. Use this prefix sum to calculate the sum of the first i+1 elements and the sum of the last n-i-1 elements. The prefixed sums allow these sums to be computed in constant time. For the entire array, calculate the absolute difference in averages at each index, keep track of the minimum difference, and return its index.
Time Complexity: O(n), where n is the length of the array, since we iterate through the array twice.
Space Complexity: O(1), no extra space is used apart from variables to store sums.
1#include <stdio.h>
2#include <stdlib.h>
3
4int minimumAverageDifference(int* nums, int numsSize) {
5 long long totalSum = 0, leftSum = 0, rightSum, minDiff = LLONG_MAX, avgDiff;
6 int minIndex = 0;
7 for (int i = 0; i < numsSize; i++) totalSum += nums[i];
8 for (int i = 0; i < numsSize; i++) {
9 leftSum += nums[i];
10 rightSum = totalSum - leftSum;
11 long long leftAvg = leftSum / (i + 1);
12 long long rightAvg = (i == numsSize - 1) ? 0 : rightSum / (numsSize - i - 1);
13 avgDiff = llabs(leftAvg - rightAvg);
14 if (avgDiff < minDiff) {
15 minDiff = avgDiff;
16 minIndex = i;
17 }
18 }
19 return minIndex;
20}
21
22int main() {
23 int nums[] = {2,5,3,9,5,3};
24 int numsSize = sizeof(nums) / sizeof(nums[0]);
25 printf("%d", minimumAverageDifference(nums, numsSize));
26 return 0;
27}This solution uses two loops: one for calculating the total sum of the array and the other for calculating the minimum average difference by using prefix sums. The prefix sums allow for a constant time calculation of the first i+1 elements and the last n-i-1 elements at each step.
This approach involves calculating total sum ahead of time and using a running sum in-place as we iterate through the array, allowing avoidance of additional space for prefix sums.
By subtracting the running sum from the total sum, we derive the right sum efficiently. Use these sums to calculate averages and determine minimal average difference efficiently.
Time Complexity: O(n)
Space Complexity: O(1)
1using System;
public class Solution {
public int FindMinAvgDiffIndex(int[] nums) {
long totalSum = 0, leftSum = 0;
int n = nums.Length, minIndex = 0;
for (int i = 0; i < n; i++) totalSum += nums[i];
long minAvgDiff = long.MaxValue;
for (int i = 0; i < n; i++) {
leftSum += nums[i];
long leftAvg = leftSum / (i + 1);
long rightAvg = i == n - 1 ? 0 : (totalSum - leftSum) / (n - i - 1);
long avgDiff = Math.Abs(leftAvg - rightAvg);
if (avgDiff < minAvgDiff) {
minAvgDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
public static void Main(String[] args) {
Solution sol = new Solution();
int[] nums = { 2, 5, 3, 9, 5, 3 };
Console.WriteLine(sol.FindMinAvgDiffIndex(nums));
}
}This C# solution uses long integer handling to manage running totals and average differences, very similar in approach to Java and C++.