2256. Minimum Average Difference

Minimum Average Difference

Problem Description

You are given a 0-indexed integer array nums of length n.

The average difference of the index i is the absolute difference between the average of the first i + 1 elements of nums and the average of the last n - i - 1 elements. Both averages should be rounded down to the nearest integer.

Return the index with the minimum average difference. If there are multiple such indices, return the smallest one.

Note:

• The absolute difference between two numbers is the absolute value of their difference.
• The average of n elements is the sum of the n elements divided (integer division) by n.
• The average of 0 elements are considered to be 0.

 

Example 1:

Input: nums = [2,5,3,9,5,3]
Output: 3

Explanation:
- The average difference of index 0 is: |2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3.
- The average difference of index 1 is: |(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2.
- The average difference of index 2 is: |(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2.
- The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0.
- The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1.
- The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

Example 2:

Input: nums = [0]
Output: 0

Explanation:
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 - 0| = |0 - 0| = 0.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

Approach) Sliding Window

This was a fairly straightforward problem, basically take the average of numbers on left, minus avg of numbers on right, and find the minimum value of that difference.

You will need to use Math floor a few times when finding the average and ABS to find the distance of left and right averages.

You could manually sum the numbers on each iteration, but I chose to do it once, then simply add or remove a single number.

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumAverageDifference = function(nums) {
   let min = Number.MAX_SAFE_INTEGER;
   let index = 0;
   for (let i = 0, left=0, right=nums.reduce((sum, curr)=>sum+curr, 0), curr; i<nums.length; i++) {
       left+=nums[i];
       right-=nums[i];
       curr = Math.abs(Math.floor(left/(i+1))-Math.floor(right/(nums.length-i-1)||0))
       if (min >curr) {
           min = curr
           index = i;
       }
   }
   return index; 
};

Approach) Brute Force

const minimumAverageDifference = function(nums) {
    const n = nums.length;
    let min = Infinity;
    let l = 1;
    let r = n-1;
    let lSum = nums[0];
    let rSum = 0;
    let minIndex = 0;
    for(let i = 1; i < n; i++) {
        rSum += nums[i];
    }
    min = Math.min(min, Math.abs(Math.floor(lSum/l) - Math.floor(rSum/r)));
    for(let i = 1; i < n-1; i++) {
        l++;
        r--;
        lSum += nums[i];
        rSum -= nums[i];
        let cur = Math.abs(Math.floor(lSum/l) - Math.floor(rSum/r));
        if(cur < min) {
            minIndex = i;
            min = cur;
        }
    }
    
    if(Math.floor(nums.reduce((a,b) => a+b)/n) < min) {
        return n-1;
    }
    
    return minIndex;
};

Approach) Prefix

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumAverageDifference = function(nums) {

    let prefixSum=[]
    let sum=0

    for(let i=0;i<nums.length;i++){
        sum+=nums[i]
        prefixSum.push(sum)
    }

    let n=nums.length

    for(let i=0;i<n;i++){
       let avg1=Math.floor(prefixSum[i]/(i+1))
       let avg2=0

       if(i===n-1){
           avg2=0
       }else{

       
       avg2=Math.floor((prefixSum[n-1]-prefixSum[i])/(n-(i+1)))
       }
       let diff=Math.abs(avg1-avg2)

       prefixSum[i]=diff
   }
 
     let min =Math.min(...prefixSum)
     let ans=Infinity


     for(let i=0;i<n;i++){
         if(prefixSum[i]===min){
            ans=Math.min(ans,i)
         }
     }

     return ans
      
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 2256. Minimum Average Difference

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!