Minimum Average Difference - Video Solutions

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(n²) 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.