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.
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; }}Video 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.