Minimum Average Difference

medium array prefix sum

Problem

Return the smallest index i minimizing |avg(nums[0..i]) − avg(nums[i+1..n−1])| where averages are integer floors. If the right side is empty, its average is 0.

Inputnums = [2, 5, 3, 9, 5, 3]

Output3

At i=3, left avg = 4, right avg = 4, diff = 0.

nums (comma-separated)

def minimum_average_difference(nums):
    n = len(nums)
    total = sum(nums)
    left = 0
    best = float('inf')
    ans = 0
    for i, x in enumerate(nums):
        left += x
        right_cnt = n - i - 1
        left_avg = left // (i + 1)
        right_avg = (total - left) // right_cnt if right_cnt > 0 else 0
        diff = abs(left_avg - right_avg)
        if diff < best:
            best = diff
            ans = i
    return ans

function minimumAverageDifference(nums) {
  const n = nums.length;
  let total = 0;
  for (const x of nums) total += x;
  let left = 0, best = Infinity, ans = 0;
  for (let i = 0; i < n; i++) {
    left += nums[i];
    const rc = n - i - 1;
    const la = Math.floor(left / (i + 1));
    const ra = rc > 0 ? Math.floor((total - left) / rc) : 0;
    const diff = Math.abs(la - ra);
    if (diff < best) { best = diff; ans = i; }
  }
  return ans;
}

class Solution {
    public int minimumAverageDifference(int[] nums) {
        int n = nums.length;
        long total = 0;
        for (int x : nums) total += x;
        long left = 0;
        long best = Long.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            left += nums[i];
            int rc = n - i - 1;
            long la = left / (i + 1);
            long ra = rc > 0 ? (total - left) / rc : 0;
            long diff = Math.abs(la - ra);
            if (diff < best) { best = diff; ans = i; }
        }
        return ans;
    }
}

int minimumAverageDifference(vector<int>& nums) {
    int n = nums.size();
    long long total = 0;
    for (int x : nums) total += x;
    long long left = 0, best = LLONG_MAX;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        left += nums[i];
        int rc = n - i - 1;
        long long la = left / (i + 1);
        long long ra = rc > 0 ? (total - left) / rc : 0;
        long long diff = abs(la - ra);
        if (diff < best) { best = diff; ans = i; }
    }
    return ans;
}

Explanation

For every split point i we need the average of the left part and the average of the right part, then the absolute difference. Recomputing both sums from scratch at each split would be slow, so we use a running prefix sum instead.

We compute total once up front. As we sweep, left grows to hold the sum of nums[0..i]. The right side's sum is then just total - left, so we never re-add anything.

The left average is left // (i + 1) and the right average is (total - left) // right_cnt, both using integer floor division as the problem requires. If the right side is empty its average is treated as 0. We track the smallest difference and remember the index where it happened.

Example: nums = [2, 5, 3, 9, 5, 3] has total 27. At i = 3 the left sum is 19 over 4 elements (avg 4) and the right sum is 8 over 2 (avg 4), so the difference is 0 — the smallest possible — making the answer index 3.

Time: O(n) Space: O(1)