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
Problem: 2256. Minimum Average Difference
Problem Link: https://leetcode.com/problems/minimum-average-difference/
Approach :
Calculate the prefix-sum and stored them in the cumSum vector.
Then for the ith index calculated the average of left numbers and the average of right numbers.
Formula :
Left = cumSum[i] / (i + 1)
Right = (cumSum[n-1] - cumSum[i]) / ((n - 1 == i)? 1 : n - i - 1Then checked for the minimum_absolute_difference.
If there is an index from which, the absolute difference is lesser than the minimum_absolute_difference, updated the final index.
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;
}
};