Problem

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5

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 <= 10^5
  • 0 <= nums[i] <= 10^5

Solution

Method 1 – Prefix Sum

Intuition

To efficiently compute the average difference for each index, we use prefix sums to get the sum of the first i+1 elements and the sum of the last n-i-1 elements. This allows us to calculate averages in O(1) time for each index.

Approach

  1. Compute the prefix sum of nums.
  2. For each index i:
    • Compute the average of the first i+1 elements: prefix[i+1] // (i+1).
    • Compute the average of the last n-i-1 elements: (total_sum - prefix[i+1]) // (n-i-1) (if n-i-1 > 0, else 0).
    • Calculate the absolute difference.
  3. Track the minimum difference and the smallest index where it occurs.
  4. Return the index with the minimum average difference.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def minimum_average_difference(nums: list[int]) -> int:
    n = len(nums)
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    total = prefix[-1]
    min_diff = float('inf')
    ans = -1
    for i in range(n):
        left_avg = prefix[i+1] // (i+1)
        right_avg = (total - prefix[i+1]) // (n-i-1) if n-i-1 > 0 else 0
        diff = abs(left_avg - right_avg)
        if diff < min_diff:
            min_diff = diff
            ans = i
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        int n = nums.size();
        vector<long long> prefix(n+1);
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + nums[i];
        long long total = prefix[n];
        int ans = -1, minDiff = INT_MAX;
        for (int i = 0; i < n; ++i) {
            int leftAvg = prefix[i+1] / (i+1);
            int rightAvg = (n-i-1 > 0) ? (total - prefix[i+1]) / (n-i-1) : 0;
            int diff = abs(leftAvg - rightAvg);
            if (diff < minDiff) {
                minDiff = diff;
                ans = i;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minimumAverageDifference(int[] nums) {
        int n = nums.length;
        long[] prefix = new long[n+1];
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + nums[i];
        long total = prefix[n];
        int ans = -1, minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            int leftAvg = (int)(prefix[i+1] / (i+1));
            int rightAvg = (n-i-1 > 0) ? (int)((total - prefix[i+1]) / (n-i-1)) : 0;
            int diff = Math.abs(leftAvg - rightAvg);
            if (diff < minDiff) {
                minDiff = diff;
                ans = i;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun minimumAverageDifference(nums: IntArray): Int {
        val n = nums.size
        val prefix = LongArray(n+1)
        for (i in nums.indices) prefix[i+1] = prefix[i] + nums[i]
        val total = prefix[n]
        var ans = -1
        var minDiff = Int.MAX_VALUE
        for (i in 0 until n) {
            val leftAvg = (prefix[i+1] / (i+1)).toInt()
            val rightAvg = if (n-i-1 > 0) ((total - prefix[i+1]) / (n-i-1)).toInt() else 0
            val diff = kotlin.math.abs(leftAvg - rightAvg)
            if (diff < minDiff) {
                minDiff = diff
                ans = i
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn minimum_average_difference(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut prefix = vec![0i64; n+1];
        for i in 0..n { prefix[i+1] = prefix[i] + nums[i] as i64; }
        let total = prefix[n];
        let mut ans = -1;
        let mut min_diff = i64::MAX;
        for i in 0..n {
            let left_avg = prefix[i+1] / (i+1) as i64;
            let right_avg = if n-i-1 > 0 { (total - prefix[i+1]) / (n-i-1) as i64 } else { 0 };
            let diff = (left_avg - right_avg).abs();
            if diff < min_diff {
                min_diff = diff;
                ans = i as i32;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minimumAverageDifference(nums: number[]): number {
        const n = nums.length;
        const prefix: number[] = [0];
        for (const x of nums) prefix.push(prefix[prefix.length-1] + x);
        const total = prefix[n];
        let ans = -1, minDiff = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i < n; ++i) {
            const leftAvg = Math.floor(prefix[i+1] / (i+1));
            const rightAvg = n-i-1 > 0 ? Math.floor((total - prefix[i+1]) / (n-i-1)) : 0;
            const diff = Math.abs(leftAvg - rightAvg);
            if (diff < minDiff) {
                minDiff = diff;
                ans = i;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
    • One pass for prefix sum, one pass for answer.
  • 🧺 Space complexity: O(n)
    • For prefix sum array.