Minimum Average Difference
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. We iterate through every possible index i from 0 to n-1. For each index, we calculate the sum of the first i+1 elements and the sum of the remaining n-i-1 elements by using two separate inner loops. Then, we compute their respective averages and the absolute difference. We keep track of the index that yields the minimum average difference found so far.
Algorithm
- Initialize
minAvgDiffto a very large number andminIndexto 0. - Iterate with an index
ifrom0ton-1, wherenis the length ofnums. - For each
i, calculate the sum of the left part (nums[0]tonums[i]) and the right part (nums[i+1]tonums[n-1]) using nested loops. Uselongfor sums to prevent overflow. - Calculate
leftAverageby dividing the left sum byi+1. - Calculate
rightAverage. If the right part has elements (i.e.,i < n-1), divide the right sum byn-i-1. Otherwise,rightAverageis 0. - Compute the
currentDiffas the absolute difference betweenleftAverageandrightAverage. - If
currentDiffis less thanminAvgDiff, updateminAvgDifftocurrentDiffandminIndextoi. - After the loop,
minIndexwill hold the result.
Walkthrough
The brute-force method involves a straightforward iteration through all possible split points. For each index i, we perform two separate summations: one for the subarray nums[0...i] and another for nums[i+1...n-1]. After getting the sums, we calculate the averages (using integer division) and find their absolute difference. We maintain a variable to track the minimum difference seen so far and the index that produced it. If we find a new smaller difference, we update our tracking variables.
class Solution { public int minimumAverageDifference(int[] nums) { int n = nums.length; if (n == 1) { return 0; } int minIndex = -1; long minAvgDiff = Long.MAX_VALUE; for (int i = 0; i < n; i++) { // Calculate sum of the first i + 1 elements long leftSum = 0; for (int j = 0; j <= i; j++) { leftSum += nums[j]; } long leftAverage = leftSum / (i + 1); // Calculate sum of the last n - i - 1 elements long rightSum = 0; int rightCount = n - 1 - i; for (int j = i + 1; j < n; j++) { rightSum += nums[j]; } long rightAverage = 0; if (rightCount > 0) { rightAverage = rightSum / rightCount; } long currentDiff = Math.abs(leftAverage - rightAverage); if (currentDiff < minAvgDiff) { minAvgDiff = currentDiff; minIndex = i; } } return minIndex; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. For each of the `n` indices, we iterate through parts of the array to calculate sums. The inner loops for summation take O(n) time in total for each outer loop iteration, leading to a quadratic time complexity. This is too slow for the given constraints.
Space
O(1). We only use a few variables to store the sums, averages, minimum difference, and the result index, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem definition without complex data structures.
Cons
Highly inefficient due to redundant calculations.
Will result in a 'Time Limit Exceeded' (TLE) error for large inputs.
The brute-force approach is slow because it repeatedly calculates sums over subarrays. This can be optimized by observing that as we move from index i to i+1, the sum of the left part can be updated in O(1) time, and consequently, the sum of the right part can also be found quickly. We can pre-calculate the total sum of the array. Then, in a single pass, we can maintain a running sum for the left part (leftSum). The sum for the right part (rightSum) can be derived by subtracting leftSum from the totalSum.
Algorithm
- First, calculate the
totalSumof all elements in thenumsarray. Use alongdata type to avoid potential integer overflow. - Initialize
minAvgDiffto a very large number,minIndexto 0, andleftSumto 0 (as along). - Iterate with an index
ifrom0ton-1. - In each iteration, update
leftSumby addingnums[i]. - Calculate
rightSumastotalSum - leftSum. - Calculate
leftAverageasleftSum / (i + 1). - Calculate
rightAverage. The number of elements in the right part isn - i - 1. If this count is zero (i.e.,i == n-1),rightAverageis 0. Otherwise, it'srightSum / (n - i - 1). - Compute the
currentDiffas the absolute difference betweenleftAverageandrightAverage. - If
currentDiffis smaller thanminAvgDiff, updateminAvgDifftocurrentDiffandminIndextoi. - After iterating through all indices,
minIndexwill be the answer.
Walkthrough
This optimized approach avoids the expensive O(n) summation inside the main loop. We start by computing the total sum of all elements in the array in a single pass. Then, we iterate from i = 0 to n-1. In each step, we maintain a leftSum which is the sum of elements from index 0 to i. This leftSum can be updated in O(1) from the previous iteration's sum. The rightSum is simply totalSum - leftSum. With both sums available in constant time, we can calculate the averages and their difference efficiently within the loop. This reduces the overall time complexity to linear.
class Solution { public int minimumAverageDifference(int[] nums) { int n = nums.length; long totalSum = 0; for (int num : nums) { totalSum += num; } int minIndex = -1; long minAvgDiff = Long.MAX_VALUE; long leftSum = 0; for (int i = 0; i < n; i++) { leftSum += nums[i]; long rightSum = totalSum - leftSum; long leftAverage = leftSum / (i + 1); long rightAverage = 0; int rightCount = n - 1 - i; if (rightCount > 0) { rightAverage = rightSum / rightCount; } long currentDiff = Math.abs(leftAverage - rightAverage); if (currentDiff < minAvgDiff) { minAvgDiff = currentDiff; minIndex = i; } } return minIndex; }}Complexity
Time
O(n), where n is the number of elements in `nums`. We have an initial pass to calculate the total sum which takes O(n), followed by a single loop through the array to calculate the differences, which also takes O(n). The total time complexity is O(n) + O(n) = O(n).
Space
O(1). We only use a constant number of variables (`totalSum`, `leftSum`, `minAvgDiff`, `minIndex`) to store our state, which does not depend on the size of the input array.
Trade-offs
Pros
Very efficient, with linear time complexity.
Optimal solution as we must visit each element at least once.
Cons
Requires careful handling of
longdata type to prevent overflow for sums.Edge case for the last index (where the right part is empty) must be handled correctly.
Solutions
Solution
class Solution {public int minimumAverageDifference(int[] nums) { int n = nums.length; long pre = 0, suf = 0; for (int x : nums) { suf += x; } int ans = 0; long mi = Long.MAX_VALUE; for (int i = 0; i < n; ++i) { pre += nums[i]; suf -= nums[i]; long a = pre / (i + 1); long b = n - i - 1 == 0 ? 0 : suf / (n - i - 1); long t = Math.abs(a - b); if (t < mi) { ans = i; mi = t; } } return ans; }}class Solution {public: int minimumAverageDifference(vector<int> &nums) { int n = nums.size(); using ll = long long; ll pre = 0; ll suf = accumulate(nums.begin(), nums.end(), 0LL); int ans = 0; ll mi = suf; for (int i = 0; i < n; ++i) { pre += nums[i]; suf -= nums[i]; ll a = pre / (i + 1); ll b = n - i - 1 == 0 ? 0 : suf / (n - i - 1); ll t = abs(a - b); if (t < mi) { ans = i; mi = t; } } return ans; }};class Solution: def minimumAverageDifference(self, nums: List[int]) -> int: pre, suf = 0, sum(nums) n = len(nums) ans, mi = 0, inf for i, x in enumerate(nums): pre += x suf -= x a = pre // (i + 1) b = 0 if n - i - 1 == 0 else suf // (n - i - 1) if (t: = abs(a - b)) < mi: ans = i mi = t return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.