Minimum Average Difference

Minimum Average Difference

What is this problem about?

The Minimum Average Difference problem asks you to find the index i in an array such that the absolute difference between the average of the first i+1 elements and the average of the remaining elements is minimized. For the last element, the "average of remaining" is considered 0. All averages should be calculated using integer division (rounded down).

Why is this asked in interviews?

This is a standard Minimum Average Difference interview question at Meta and Amazon. It tests a candidate's ability to optimize array calculations using Prefix Sums. It evaluates whether you can avoid $O(N^2)$ complexity by pre-calculating the total sum and updating the "left sum" and "right sum" in a single pass.

Algorithmic pattern used

The Prefix Sum / Total Sum interview pattern is perfect here.

1. Calculate the total sum of the array first.
2. Initialize left_sum = 0.
3. Iterate through the array:
   • Add nums[i] to left_sum.
   • right_sum = total_sum - left_sum.
   • Calculate left_avg = left_sum // (i + 1).
   • Calculate right_avg = right_sum // (n - i - 1) (handle the case where n-i-1 == 0).
   • Find the absolute difference and update the minimum.

Example explanation

Array [2, 5, 3, 4], total sum = 14.

1. i = 0: Left sum = 2, Left avg = 2. Right sum = 12, Right avg = 12/3 = 4. Diff = 2.
2. i = 1: Left sum = 7, Left avg = 7/2 = 3. Right sum = 7, Right avg = 7/2 = 3. Diff = 0.
3. i = 2: Left sum = 10, Left avg = 10/3 = 3. Right sum = 4, Right avg = 4/1 = 4. Diff = 1. Minimum difference is 0 at index 1.

Common mistakes candidates make

• Integer division by zero: Forgetting to handle the last index where the count of "remaining elements" is zero.
• O(N^2) approach: Recalculating the left and right sums for every index using a nested loop.
• Large sum overflow: In languages like Java or C++, not using long for sums, leading to overflow errors with large arrays.

Interview preparation tip

Whenever a problem involves "left side" and "right side" of an index, the Prefix Sum interview pattern is your first tool. It turns multiple linear scans into $O(1)$ lookups. This is a fundamental skill for any coding interview.