Minimum Average Difference solution and explanation
9 more videos on this problem
Minimum Average Difference-(Amazon, Paytm) : Explanation ➕ Live CodingcodestorywithMIK · 21:47 · 6K views
2256 Minimum Average Difference | Zero to FAANG | Assignment Solution | Leetcode | Striver | WE2Programmers Zone · 18:20 · 1K views
2256. Minimum Average Difference (Leetcode Medium)Programming Live with Larry · 7:08 · 668 views
Daily Leetcode #978: Dec 04, 2022 - 2256. Minimum Average DifferenceProgramming Live with Larry · 6:12 · 558 views
2256 || Minimum Average Difference || Leetcode Daily ChallengeCodeFreaks · 11:08 · 541 views
2256 - Minimum Average Difference🔥🔥 | Prefix Sum | Leetcode Daily ChallengeTechBits by Vismay · 9:29 · 372 views
[Java / C++] Minimum Average Difference | LEETCODE - 2256 | Easy solutionhi-malik · 17:56 · 304 views
2256. Minimum Average Difference | Python | MANG - Amazon Question | Leetcode | English | code iocode io - English · 29:57 · 250 views
2256. Minimum Average Difference - LeetCode Python SolutionCode with Carter · 11:06 · 245 views
2256. Minimum Average Difference | JavaScript | LeetCode Daily Challenge | Easy UnderstandingLeetCodeWithMonu · 10:34 · 211 views
The problem
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 of two numbers is the absolute value of their difference.
- The average of
nelements is the sum of thenelements divided (integer division) byn. - The average of
0elements is considered to be0.
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 <= 1050 <= nums[i] <= 105
Approach overview
Problem Overview: You are given an integer array nums. For every index i, compute the average of the first i + 1 elements and the average of the remaining elements to the right. The goal is to return the index where the absolute difference between these two averages is minimized.
Approach 1: Brute Force Average Calculation (O(n2) time, O(1) space)
The straightforward approach evaluates every possible split point in the array. For each index i, iterate through the left part to compute its sum and average, then iterate through the right part to compute its sum and average. After computing both averages, take the absolute difference and track the smallest value seen so far. This works but repeatedly recomputes sums for overlapping subarrays, leading to quadratic time complexity. It is useful for understanding the definition of the problem but becomes too slow for large arrays.
Approach 2: Prefix Sum Technique (O(n) time, O(n) space)
The key observation is that averages depend on sums, and sums of prefixes can be reused. Build a prefix sum array where prefix[i] stores the sum of elements from index 0 to i. The total array sum is prefix[n-1]. For each index, compute the left average using prefix[i] / (i + 1) and the right average using (totalSum - prefix[i]) / (n - i - 1). If there are no elements on the right, the right average is defined as 0. Track the minimum absolute difference and its index as you iterate once through the array. This approach eliminates repeated summations and is the standard optimization when working with cumulative ranges using prefix sum. The iteration itself is linear, making the total time complexity O(n).
Approach 3: In-place Running Sums (O(n) time, O(1) space)
You can remove the extra prefix array by maintaining running sums during traversal. First compute the total sum of the array. Then iterate from left to right while keeping a leftSum. At index i, add nums[i] to leftSum, compute the right sum as totalSum - leftSum, and derive both averages using integer division. The left count is i + 1 and the right count is n - i - 1. Update the minimum difference and index during the scan. This approach keeps the same linear time as the prefix method but reduces memory usage to constant space. It’s a common optimization when solving problems on arrays where only cumulative totals are required.
Recommended for interviews: Interviewers expect the linear-time solution using prefix sums or running sums. Starting with the brute force explanation shows you understand the definition of the averages, but optimizing it with cumulative sums demonstrates algorithmic thinking and familiarity with the prefix sum pattern. The in-place running sum variant is usually considered the cleanest implementation because it achieves O(n) time with O(1) extra space.
Approach 1: Prefix Sum Technique
The idea is to use prefix sums to efficiently calculate the sum of elements up to any index and from any index to the end.
First, compute the prefix sum of the array. Use this prefix sum to calculate the sum of the first i+1 elements and the sum of the last n-i-1 elements. The prefixed sums allow these sums to be computed in constant time. For the entire array, calculate the absolute difference in averages at each index, keep track of the minimum difference, and return its index.
def minimumAverageDifference(nums):
total_sum = sum(nums)
left_sum = 0
min_diff = float('inf')
min_index = 0
for i in range(len(nums)):
left_sum += nums[i]
left_avg = left_sum // (i + 1)
right_avg = 0 if i == len(nums) - 1 else (total_sum - left_sum) // (len(nums) - i - 1)
avg_diff = abs(left_avg - right_avg)
if avg_diff < min_diff:
min_diff = avg_diff
min_index = i
return min_index
nums = [2, 5, 3, 9, 5, 3]
print(minimumAverageDifference(nums))import java.util.*;
class Solution {
public int minimumAverageDifference(int[] nums) {
long totalSum = 0, leftSum = 0;
int n = nums.length, minIndex = 0;
for (int num : nums) totalSum += num;
long minDiff = Long.MAX_VALUE;
for (int i = 0; i < n; ++i) {
leftSum += nums[i];
long leftAvg = leftSum / (i + 1);
long rightAvg = (i == n - 1) ? 0 : (totalSum - leftSum) / (n - i - 1);
long avgDiff = Math.abs(leftAvg - rightAvg);
if (avgDiff < minDiff) {
minDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2,5,3,9,5,3};
System.out.println(sol.minimumAverageDifference(nums));
}
}#include <iostream>
#include <vector>
#include <climits>
int minimumAverageDifference(std::vector<int>& nums) {
long long totalSum = 0, leftSum = 0;
int n = nums.size(), minIndex = 0;
for (int num : nums) totalSum += num;
long long minDiff = LLONG_MAX;
for (int i = 0; i < n; ++i) {
leftSum += nums[i];
long long leftAvg = leftSum / (i + 1);
long long rightAvg = (i == n - 1) ? 0 : (totalSum - leftSum) / (n - i - 1);
long long avgDiff = std::abs(leftAvg - rightAvg);
if (avgDiff < minDiff) {
minDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
int main() {
std::vector<int> nums = {2,5,3,9,5,3};
std::cout << minimumAverageDifference(nums);
return 0;
}function minimumAverageDifference(nums) {
let totalSum = nums.reduce((a, b) => a + b, 0);
let leftSum = 0;
let minDiff = Number.MAX_VALUE;
let minIndex = 0;
for (let i = 0; i < nums.length; i++) {
leftSum += nums[i];
const leftAvg = Math.floor(leftSum / (i + 1));
const rightAvg = i === nums.length - 1 ? 0 : Math.floor((totalSum - leftSum) / (nums.length - i - 1));
const avgDiff = Math.abs(leftAvg - rightAvg);
if (avgDiff < minDiff) {
minDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
const nums = [2, 5, 3, 9, 5, 3];
console.log(minimumAverageDifference(nums));#include <stdio.h>
#include <stdlib.h>
int minimumAverageDifference(int* nums, int numsSize) {
long long totalSum = 0, leftSum = 0, rightSum, minDiff = LLONG_MAX, avgDiff;
int minIndex = 0;
for (int i = 0; i < numsSize; i++) totalSum += nums[i];
for (int i = 0; i < numsSize; i++) {
leftSum += nums[i];
rightSum = totalSum - leftSum;
long long leftAvg = leftSum / (i + 1);
long long rightAvg = (i == numsSize - 1) ? 0 : rightSum / (numsSize - i - 1);
avgDiff = llabs(leftAvg - rightAvg);
if (avgDiff < minDiff) {
minDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
int main() {
int nums[] = {2,5,3,9,5,3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d", minimumAverageDifference(nums, numsSize));
return 0;
}using System;
public class Solution {
public int MinimumAverageDifference(int[] nums) {
long totalSum = 0, leftSum = 0;
int n = nums.Length, minIndex = 0;
foreach (int num in nums) totalSum += num;
long minDiff = long.MaxValue;
for (int i = 0; i < n; ++i) {
leftSum += nums[i];
long leftAvg = leftSum / (i + 1);
long rightAvg = (i == n - 1) ? 0 : (totalSum - leftSum) / (n - i - 1);
long avgDiff = Math.Abs(leftAvg - rightAvg);
if (avgDiff < minDiff) {
minDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {2, 5, 3, 9, 5, 3};
Console.WriteLine(sol.MinimumAverageDifference(nums));
}
}This Python solution computes prefix sums while iterating over the list, and simultaneously evaluates the absolute difference between left and right averages at each index.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: In-place Running Sums
This approach involves calculating total sum ahead of time and using a running sum in-place as we iterate through the array, allowing avoidance of additional space for prefix sums.
By subtracting the running sum from the total sum, we derive the right sum efficiently. Use these sums to calculate averages and determine minimal average difference efficiently.
def findMinAvgDiffIndex(nums):
total_sum = sum(nums)
left_sum = 0
min_diff = float('inf')
min_index = 0
for i in range(len(nums)):
left_sum += nums[i]
left_avg = left_sum // (i + 1)
right_avg = 0 if i == len(nums) - 1 else (total_sum - left_sum) // (len(nums) - i - 1)
avg_diff = abs(left_avg - right_avg)
if avg_diff < min_diff:
min_diff = avg_diff
min_index = i
return min_index
nums = [2, 5, 3, 9, 5, 3]
print(findMinAvgDiffIndex(nums))class Solution {
public int findMinAvgDiffIndex(int[] nums) {
long totalSum = 0, leftSum = 0;
int n = nums.length, minIndex = 0;
for (int num : nums) totalSum += num;
long minAvgDiff = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
leftSum += nums[i];
long leftAvg = leftSum / (i + 1);
long rightAvg = i == n - 1 ? 0 : (totalSum - leftSum) / (n - i - 1);
long avgDiff = Math.abs(leftAvg - rightAvg);
if (avgDiff < minAvgDiff) {
minAvgDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 5, 3, 9, 5, 3};
System.out.println(sol.findMinAvgDiffIndex(nums));
}
}#include <iostream>
#include <vector>
#include <climits>
int findMinAvgDiffIndex(std::vector<int>& nums) {
long long totalSum = 0, leftSum = 0;
int n = nums.size(), minIndex = 0;
for (auto& num : nums) totalSum += num;
long long minAvgDiff = LLONG_MAX;
for (int i = 0; i < n; i++) {
leftSum += nums[i];
long long leftAvg = leftSum / (i + 1);
long long rightAvg = i == n - 1 ? 0 : (totalSum - leftSum) / (n - i - 1);
long long avgDiff = std::abs(leftAvg - rightAvg);
if (avgDiff < minAvgDiff) {
minAvgDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
int main() {
std::vector<int> nums = {2, 5, 3, 9, 5, 3};
std::cout << findMinAvgDiffIndex(nums) << std::endl;
return 0;
}function findMinAvgDiffIndex(nums) {
let totalSum = nums.reduce((a, b) => a + b, 0);
let leftSum = 0;
let minDiff = Number.MAX_VALUE;
let minIndex = 0;
for (let i = 0; i < nums.length; i++) {
leftSum += nums[i];
const leftAvg = Math.floor(leftSum / (i + 1));
const rightAvg = i === nums.length - 1 ? 0 : Math.floor((totalSum - leftSum) / (nums.length - i - 1));
const avgDiff = Math.abs(leftAvg - rightAvg);
if (avgDiff < minDiff) {
minDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
const nums = [2, 5, 3, 9, 5, 3];
console.log(findMinAvgDiffIndex(nums));#include <stdio.h>
#include <stdlib.h>
int findMinAvgDiffIndex(int* nums, int numsSize) {
long long totalSum = 0;
long long leftSum = 0;
for (int i = 0; i < numsSize; i++) {
totalSum += nums[i];
}
long long minAvgDiff = LLONG_MAX;
int minIndex = 0;
for (int i = 0; i < numsSize; i++) {
leftSum += nums[i];
long long leftAvg = leftSum / (i + 1);
long long rightAvg = (i == numsSize - 1) ? 0 : (totalSum - leftSum) / (numsSize - i - 1);
long long avgDiff = llabs(leftAvg - rightAvg);
if (avgDiff < minAvgDiff) {
minAvgDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
int main() {
int nums[] = {2,5,3,9,5,3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d", findMinAvgDiffIndex(nums, numsSize));
return 0;
}using System;
public class Solution {
public int FindMinAvgDiffIndex(int[] nums) {
long totalSum = 0, leftSum = 0;
int n = nums.Length, minIndex = 0;
for (int i = 0; i < n; i++) totalSum += nums[i];
long minAvgDiff = long.MaxValue;
for (int i = 0; i < n; i++) {
leftSum += nums[i];
long leftAvg = leftSum / (i + 1);
long rightAvg = i == n - 1 ? 0 : (totalSum - leftSum) / (n - i - 1);
long avgDiff = Math.Abs(leftAvg - rightAvg);
if (avgDiff < minAvgDiff) {
minAvgDiff = avgDiff;
minIndex = i;
}
}
return minIndex;
}
public static void Main(String[] args) {
Solution sol = new Solution();
int[] nums = { 2, 5, 3, 9, 5, 3 };
Console.WriteLine(sol.FindMinAvgDiffIndex(nums));
}
}This Python solution calculates the running sum on the fly while iterating, allowing calculation of differences without the need for explicit prefix arrays and reducing overhead.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Traverse
We directly traverse the array nums. For each index i, we maintain the sum of the first i+1 elements pre and the sum of the last n-i-1 elements suf. We calculate the absolute difference of the average of the first i+1 elements and the average of the last n-i-1 elements, denoted as t. If t is less than the current minimum value mi, we update the answer ans=i and the minimum value mi=t.
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function minimumAverageDifference(nums: number[]): number {
const n = nums.length;
let pre = 0;
let suf = nums.reduce((a, b) => a + b);
let ans = 0;
let mi = suf;
for (let i = 0; i < n; ++i) {
pre += nums[i];
suf -= nums[i];
const a = Math.floor(pre / (i + 1));
const b = n - i - 1 === 0 ? 0 : Math.floor(suf / (n - i - 1));
const t = Math.abs(a - b);
if (t < mi) {
ans = i;
mi = t;
}
}
return ans;
}func minimumAverageDifference(nums []int) (ans int) {
n := len(nums)
pre, suf := 0, 0
for _, x := range nums {
suf += x
}
mi := suf
for i, x := range nums {
pre += x
suf -= x
a := pre / (i + 1)
b := 0
if n-i-1 != 0 {
b = suf / (n - i - 1)
}
if t := abs(a - b); t < mi {
ans = i
mi = t
}
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Technique | Time Complexity: O(n) |
| In-place Running Sums | Time Complexity: O(n) |
| Traverse | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Average Calculation | O(n^2) | O(1) | Useful for understanding the definition of prefix/suffix averages or validating small inputs |
| Prefix Sum Technique | O(n) | O(n) | When prefix arrays are acceptable and you want clear separation of cumulative sums |
| In-place Running Sums | O(n) | O(1) | Best for interviews and memory-constrained environments |
Frequently asked questions
Is Minimum Average Difference easy or hard?
Minimum Average Difference is classified as a Medium problem. The challenge lies in recognizing that recomputing sums repeatedly is inefficient and that prefix sums can reduce the complexity from O(n^2) to O(n). Once the prefix pattern is recognized, the implementation is straightforward.
Minimum Average Difference Python/Java solution
Python, Java, C++, C#, and JavaScript implementations all follow the same logic: compute the total sum, iterate through the array while maintaining a running prefix sum, calculate both averages at each index, and track the minimum difference. The algorithm remains O(n) regardless of language.
How to solve Minimum Average Difference in O(n)?
First compute the total sum of the array. Traverse the array while maintaining a running prefix sum. At each index, compute the left average using the prefix sum and the right average using totalSum minus prefixSum. Track the smallest absolute difference and return the corresponding index after the traversal.
What is the best approach for Minimum Average Difference?
The optimal approach uses prefix sums or running sums to compute averages in a single pass. By keeping track of the cumulative sum of elements and the remaining suffix sum, you can evaluate each index in O(n) time. The in-place running sum variant is often preferred because it also achieves O(1) extra space.
Is Minimum Average Difference asked at Google/Amazon/Meta?
Array and prefix sum problems like Minimum Average Difference appear frequently in technical interviews at companies such as Amazon, Google, and Meta. They test your ability to optimize repeated computations and recognize cumulative sum patterns that reduce time complexity.
What data structure is used in Minimum Average Difference?
The problem primarily uses arrays along with the prefix sum technique. Instead of advanced data structures, the solution relies on cumulative arithmetic calculations to efficiently derive subarray sums and averages.
What is the time complexity of Minimum Average Difference?
The optimal solution runs in O(n) time because the array is scanned once while maintaining cumulative sums. Each index performs constant-time arithmetic operations to compute prefix and suffix averages. Space complexity can be either O(n) with a prefix array or O(1) with running sums.