Skip to main content
Talentd

Minimum Average Difference - Solution & Explanation

MediumArrayPrefix Sum22 min readAsked at: Amazon, Meta
Practice this problem

Problem Statement

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 n elements is the sum of the n elements divided (integer division) by n.
  • The average of 0 elements is considered to be 0.

 

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 <= 105
  • 0 <= 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.

This solution uses two loops: one for calculating the total sum of the array and the other for calculating the minimum average difference by using prefix sums. The prefix sums allow for a constant time calculation of the first i+1 elements and the last n-i-1 elements at each step.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array, since we iterate through the array twice.
Space Complexity: O(1), no extra space is used apart from variables to store sums.

Try this approach in the editor →

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.

In this approach, instead of explicitly creating a prefix sum array, we modify the running total inline during the loop, making it both time- and space-efficient.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum Technique

Time Complexity: O(n), where n is the length of the array, since we iterate through the array twice.
Space Complexity: O(1), no extra space is used apart from variables to store sums.

In-place Running Sums

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

Traverse—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Average CalculationO(n^2)O(1)Useful for understanding the definition of prefix/suffix averages or validating small inputs
Prefix Sum TechniqueO(n)O(n)When prefix arrays are acceptable and you want clear separation of cumulative sums
In-place Running SumsO(n)O(1)Best for interviews and memory-constrained environments

Video Solution

Minimum Average Difference-(Amazon, Paytm) : Explanation ➕ Live Coding • codestorywithMIK • 6,505 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Average Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Ways to Split Array

Next

Split Array With Same Average