hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Minimum Average Difference


  • Approach :

    1. Calculate the prefix-sum and stored them in the cumSum vector.

    2. Then for the ith index calculated the average of left numbers and the average of right numbers.

    3. Formula :
      Left = cumSum[i] / (i + 1)
      Right = (cumSum[n-1] - cumSum[i]) / ((n - 1 == i)? 1 : n - i - 1

    4. Then checked for the minimum_absolute_difference.

    5. If there is an index from which, the absolute difference is lesser than the minimum_absolute_difference, updated the final index.

    6. And returned finally updated index.


  • Time and Space Complexity :

      • Time complexity: O(n)

      • Space complexity: O(n)


Code [C++]

class Solution {

public:

int minimumAverageDifference(vector<int>& nums) {

int n = nums.size();

vector<long long>cumSum(n, 0);

cumSum[0] = nums[0];

long long Left = 0, Right = 0, minimum_abs_diff = LLONG_MAX;

int ans;


for(int i=1; i<n; i++){

cumSum[i] = cumSum[i-1] + (long long)nums[i];

}


for(int i=0; i<n; i++){

Left = cumSum[i] / (i + 1);

Right = (cumSum[n-1] - cumSum[i]) / ((n - 1 == i)? 1 : n - i - 1);

int abs_diff = abs(Left - Right);

if(abs_diff < minimum_abs_diff){

minimum_abs_diff = abs_diff;

ans = i;

}

}

return ans;

}

};