Minimum Average Difference

Medium
1152.

Minimum Average Difference

Minimum Average Difference is a medium coding problem on arrays and prefix sum, asked in Amazon and Microsoft interviews.

For an index i of the 0-indexed array nums (length n), the average difference is the absolute difference between:

  • the average of the first i + 1 elements, and
  • the average of the last n - i - 1 elements.

Both averages are rounded down to the nearest integer, and the average of zero elements is taken to be 0.

Return the index with the minimum average difference. If several indices tie, return the smallest one.

Example 1

Input
nums = [3,8,1,6,2]
Output
2
Explanation
At index 2 the first three elements average 12 / 3 = 4 and the last two average 8 / 2 = 4, a difference of 0.

Example 2

Input
nums = [0]
Output
0
Explanation
The only index: 0 versus the empty average 0.

Example 3

Input
nums = [5,5,5,1]
Output
0
Explanation
Indices 0 and 1 both give a difference of 2; the smaller index wins.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumAverageDifference = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Average Difference — Solution in Python, Java & C++

Minimum Average Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Average Difference is a medium coding problem on arrays and prefix sum, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

For an index i of the 0-indexed array nums (length n), the average difference is the absolute difference between:

  • the average of the first i + 1 elements, and
  • the average of the last n - i - 1 elements.

Both averages are rounded down to the nearest integer, and the average of zero elements is taken to be 0.

Return the index with the minimum average difference. If several indices tie, return the smallest one.

Example 1

Input: nums = [3,8,1,6,2]
Output: 2
Explanation: At index 2 the first three elements average 12 / 3 = 4 and the last two average 8 / 2 = 4, a difference of 0.

Example 2

Input: nums = [0]
Output: 0
Explanation: The only index: 0 versus the empty average 0.

Example 3

Input: nums = [5,5,5,1]
Output: 0
Explanation: Indices 0 and 1 both give a difference of 2; the smaller index wins.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

Hints for Minimum Average Difference

  1. Hint 1

    Recomputing both sums for every index is quadratic. What can you precompute?

  2. Hint 2

    With the total sum and a running prefix sum, the suffix sum is total - prefix.

  3. Hint 3

    Sums reach 10^10, so keep them in 64-bit integers; remember the right side is empty at the last index.

How to solve Minimum Average Difference

A running prefix sum plus the total gives both sides' sums at every index in O(1), so one pass evaluates every candidate.

Approach

  1. Compute total, the sum of all elements (in 64-bit).
  2. Sweep i from left to right, adding nums[i] to prefix.
  3. Left average is prefix / (i + 1); right average is (total - prefix) / (n - i - 1), or 0 when i = n - 1.
  4. Track the smallest absolute difference, updating only on a strict improvement so the first index wins ties.

Why it works

The two sums are exactly the prefix and suffix sums at i, and the averages are floor divisions of non-negative numbers, so integer division matches the definition. Strictly-smaller updates during a left-to-right sweep keep the earliest index among equal differences.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • At i = n - 1 the right side is empty — guard the division by zero and use 0.
  • The sums overflow 32-bit integers (up to 10^5 * 10^5).
  • Use <, not <=, when comparing differences, or a later index steals the tie.

Reference solution

Python

from typing import List

def minimumAverageDifference(nums: List[int]) -> int:
    n = len(nums)
    total = sum(nums)
    prefix = 0
    best, best_diff = 0, -1
    for i in range(n):
        prefix += nums[i]
        left = prefix // (i + 1)
        right = (total - prefix) // (n - i - 1) if n - i - 1 > 0 else 0
        d = abs(left - right)
        if best_diff < 0 or d < best_diff:
            best_diff = d
            best = i
    return best

Java

public static int minimumAverageDifference(int[] nums) {
    int n = nums.length;
    long total = 0;
    for (int x : nums) total += x;
    long prefix = 0, bestDiff = -1;
    int best = 0;
    for (int i = 0; i < n; i++) {
        prefix += nums[i];
        long left = prefix / (i + 1);
        long right = n - i - 1 > 0 ? (total - prefix) / (n - i - 1) : 0;
        long d = Math.abs(left - right);
        if (bestDiff < 0 || d < bestDiff) {
            bestDiff = d;
            best = i;
        }
    }
    return best;
}

C++

int minimumAverageDifference(vector<int>& nums) {
    int n = nums.size();
    long long total = 0;
    for (int x : nums) total += x;
    long long prefix = 0, bestDiff = -1;
    int best = 0;
    for (int i = 0; i < n; i++) {
        prefix += nums[i];
        long long left = prefix / (i + 1);
        long long right = n - i - 1 > 0 ? (total - prefix) / (n - i - 1) : 0;
        long long d = left > right ? left - right : right - left;
        if (bestDiff < 0 || d < bestDiff) {
            bestDiff = d;
            best = i;
        }
    }
    return best;
}

JavaScript

var minimumAverageDifference = function(nums) {
    var n = nums.length;
    var total = 0;
    for (var i = 0; i < n; i++) total += nums[i];
    var prefix = 0, best = 0, bestDiff = -1;
    for (var j = 0; j < n; j++) {
        prefix += nums[j];
        var left = Math.floor(prefix / (j + 1));
        var right = n - j - 1 > 0 ? Math.floor((total - prefix) / (n - j - 1)) : 0;
        var d = Math.abs(left - right);
        if (bestDiff < 0 || d < bestDiff) {
            bestDiff = d;
            best = j;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum