2256. Minimum Average Difference

Hello, reader 👋🏽 ! Welcome to day 64 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 2256. Minimum Average Difference.

🤔 Problem Statement

Given a 0-indexed integer array nums of length n, return the smallest minimum average difference.
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.
If there are multiple such indices, return the smallest one.
Note:
- The absolute difference of 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 is considered to be 0.
E.g.:
- nums = [2,5,3,9,5,3] => 3

💬 Thought Process - Prefix Sum

To calculate the average difference at index i, we require the sum of elements until i as well as the sum of elements from i to n-1.
The sum of elements at every index from index 0 to i can be calculated while iterating and finding the average at every index.
To find the sum of elements from index i+1 to n-1, we can simply subtract the prefix sum from the total sum of the array elements.
Let's illustrate with an example: [2,5,3,9]. Let's initialise prefix sum to 0. total sum = 19
- i = 0
  - Sum of elements till 0 (i)
    - prefix sum = prefix sum + nums[0] => 0 + 2 = 2
  - Sum of elements from i+1 (1) to n-1
    - total sum - prefix sum => 19 - 2 = 17
  - Left average = 2/1 = 2
  - Right average = 17/3 = 5
  - Difference = abs(3 - 5) = 2
- i = 1
  - Sum of elements till 1 (i)
    - prefix sum = prefix sum + nums[1] => 2 + 5 = 7
  - Sum of elements from i+1 (2) to n-1
    - total sum - prefix sum => 19 - 7 = 14
  - Left average = 7/1 = 3
  - Right average = 12/2 = 6
  - Difference = abs(3 - 6) = 3
- i = 2
  - Sum of elements till 2 (i)
    - prefix sum = prefix sum + nums[2] => 7 + 3 = 10
  - Sum of elements from i+1 (3) to n-1
    - total sum - prefix sum => 19 - 10 = 9
  - Left average = 10/3 = 3
  - Right average = 9/1 = 9
  - Difference = abs(3 - 9) = 6
- i = 3
  - Sum of elements till 3 (i)
    - prefix sum = prefix sum + nums[3] => 10 + 9 = 19
  - Sum of elements from i+1 (4) to n-1
    - total sum - prefix sum => 19 - 19 = 0
  - Left average = 19/4 = 4
  - Right average = 0 (Given in the question that avg(0) = 0)
  - Difference = abs(4 - 0) = 4
From all these average differences at every index, the minimum is at index 0 and 1. Since the index 0 is smaller than 1, the answer for [2,5,3,9] is 0.
That's it, We are done! Let's look at the code now keeping in mind the calculations at every index.

👩🏽‍💻 Solution - Prefix Sum

Below is the code for the approach using one pass iteration and count.

class Solution {
    public int minimumAverageDifference(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        long prefixSum = 0;
        long total = 0;
        long minAverageDiff = Integer.MAX_VALUE;
        int minAvgIndex = -1;

        for(int num: nums) {
            total += num;
        }

        for(int i = 0; i<n; i++) {
            prefixSum += (long) nums[i];
            long right = (total - prefixSum);

            long leftAvg = prefixSum / (i+1); 
            long rightAvg = 0;
            if(i+1 != n) {
                rightAvg = right / (n-i-1);
            }

            long diff = Math.abs(leftAvg - rightAvg);

            if(diff < minAverageDiff) {
                minAvgIndex = i;
                minAverageDiff = diff;
            }
        }

        return minAvgIndex;
    }
}

Time Complexity: O(n)
  - n = number of elements in the array
Space Complexity: O(1)

You can find the link to the GitHub repo for this question here: 2256. Minimum Average Difference.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian