# Minimum Average Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-average-difference)
Canonical: https://scaleengineer.com/dsa/problems/minimum-average-difference
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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 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 `n` elements is the **sum** of the `n` elements divided (**integer division**) by `n`.
* The average of `0` elements is considered to be `0`.

**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 <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize `minAvgDiff` to a very large number and `minIndex` to 0.
- Iterate with an index `i` from `0` to `n-1`, where `n` is the length of `nums`.
- For each `i`, calculate the sum of the left part (`nums[0]` to `nums[i]`) and the right part (`nums[i+1]` to `nums[n-1]`) using nested loops. Use `long` for sums to prevent overflow.
- Calculate `leftAverage` by dividing the left sum by `i+1`.
- Calculate `rightAverage`. If the right part has elements (i.e., `i < n-1`), divide the right sum by `n-i-1`. Otherwise, `rightAverage` is 0.
- Compute the `currentDiff` as the absolute difference between `leftAverage` and `rightAverage`.
- If `currentDiff` is less than `minAvgDiff`, update `minAvgDiff` to `currentDiff` and `minIndex` to `i`.
- After the loop, `minIndex` will hold the result.

## Single Pass with Prefix Sum
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`.
**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.
**Pros:** Very efficient, with linear time complexity.; Optimal solution as we must visit each element at least once.
**Cons:** Requires careful handling of `long` data type to prevent overflow for sums.; Edge case for the last index (where the right part is empty) must be handled correctly.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- First, calculate the `totalSum` of all elements in the `nums` array. Use a `long` data type to avoid potential integer overflow.
- Initialize `minAvgDiff` to a very large number, `minIndex` to 0, and `leftSum` to 0 (as a `long`).
- Iterate with an index `i` from `0` to `n-1`.
- In each iteration, update `leftSum` by adding `nums[i]`.
- Calculate `rightSum` as `totalSum - leftSum`.
- Calculate `leftAverage` as `leftSum / (i + 1)`.
- Calculate `rightAverage`. The number of elements in the right part is `n - i - 1`. If this count is zero (i.e., `i == n-1`), `rightAverage` is 0. Otherwise, it's `rightSum / (n - i - 1)`.
- Compute the `currentDiff` as the absolute difference between `leftAverage` and `rightAverage`.
- If `currentDiff` is smaller than `minAvgDiff`, update `minAvgDiff` to `currentDiff` and `minIndex` to `i`.
- After iterating through all indices, `minIndex` will be the answer.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```