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 + 1elements, and - the average of the last
n - i - 1elements.
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^50 <= nums[i] <= 10^5
Hints for Minimum Average Difference
Hint 1
Recomputing both sums for every index is quadratic. What can you precompute?
Hint 2
With the total sum and a running prefix sum, the suffix sum is
total - prefix.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
- Compute
total, the sum of all elements (in 64-bit). - Sweep
ifrom left to right, addingnums[i]toprefix. - Left average is
prefix / (i + 1); right average is(total - prefix) / (n - i - 1), or 0 wheni = n - 1. - 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 - 1the 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 bestJava
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