Problem Statement

Given a non-negative integer array nums, you need to find an index i such that the absolute difference between the average of the first i + 1 elements and the average of the last n - i - 1 elements is minimized.

If there is only one element in the array, the average of the last part is considered to be zero. Return the index i where this minimum absolute difference occurs.

Both averages should be rounded down to the nearest integer.

Examples

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

Explanantion:
The only index is 0 so return 0.
The average difference of index 0 is |0/1 - 0| = |0 - 0| = 0

Example 3:

Input: nums = [4, 2, 0]
Output: 2

Explanation:
For i = 0: left average = 4, right average = (2 + 0)/ 2 = 1; diff = |4 - 1| = 3
For i = 1: Left Average = (4 + 2) / 2 = 3, Right Average = 0; Diff = |3 - 0| = 3
For i = 2: Left Average = (4 + 2 + 0) / 3 = 2, Right Average = 0; Diff = |2 - 0| = 2
Minimum diff occurs at index 2.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

For each index i, calculate the left average and the right average by iterating over the array. This approach checks every possible split point in the array.

Steps:

1. Loop through each index i from 0 to n - 1.
2. For each i, calculate the left sum and right sum by iterating over the relevant parts of the array.
3. Compute the averages and their difference.
4. Track the index that gives the minimum difference.

Code:

#include <vector>
#include <cmath>
#include <limits>

using namespace std;

// Function to find the index with the minimum average difference using brute force
int minimumAverageDifferenceBruteForce(vector<int>& nums) {
    int n = nums.size(); // Get the size of the input array
    int minDiff = INT_MAX; // Initialize minimum difference to maximum integer value
    int index = 0; // Initialize index for the minimum difference

    // Loop through each index to calculate averages
    for (int i = 0; i < n; i++) {
        int leftSum = 0;
        // Calculate the sum of the left part (first i + 1 elements)
        for (int j = 0; j <= i; j++) {
            leftSum += nums[j];
        }

        int rightSum = 0;
        // Calculate the sum of the right part (remaining elements)
        for (int j = i + 1; j < n; j++) {
            rightSum += nums[j];
        }

        int leftCount = i + 1; // Count of elements in the left part
        int rightCount = n - leftCount; // Count of elements in the right part
        
        // Calculate the averages
        int leftAverage = leftSum / leftCount;
        int rightAverage = (rightCount > 0) ? (rightSum / rightCount) : 0; // If rightCount is 0, average is 0

        // Calculate the absolute difference between the two averages
        int diff = abs(leftAverage - rightAverage);
        
        // Update the minimum difference and index if a new minimum is found
        if (diff < minDiff) {
            minDiff = diff;
            index = i;
        }
    }

    return index; // Return the index with the minimum average difference
}

Complexity Analysis:

• Time Complexity: O(n^2)
  • For each index, we iterate through the array elements.
• Space Complexity: O(1)
  • Only a constant amount of space is used.

2️⃣ Prefix Sums

Intuition:

This approach uses prefix sums to calculate the left and right sums more efficiently, avoiding the need for nested loops.

Steps:

1. Compute the total sum of the array.
2. Maintain a running left sum as we iterate through the array.
3. Calculate the right sum based on the total sum and the left sum.
4. Update averages and find the minimum difference in a single pass.

Note:

Do Handle for division by zero when the whole array is left part and 0 as the right part.

long long rightAverage = (i == n - 1) ? 0 : rightSum / rightCount;

OR

long long rightAverage;
if (i == n - 1) {
   	rightAverage = 0;
} else {
	rightAverage = righSum / rightCount;
}

Code:

 #include <vector>
#include <limits>
#include <cmath> // For abs

using namespace std;

// Function to find the index with the minimum average difference
int minimumAverageDifference(vector<int>& nums) {
    int n = nums.size(); // Get the size of the input array
    
    // Calculate the total sum of the array
    long long totalSum = 0;
    for (int i = 0; i < n; i++) {
        totalSum += nums[i];
    }
    
    long long leftSum = 0; // Cumulative sum of elements from the left
    long long rightSum = 0; // Cumulative sum of elements from the right (derived from total sum)
    
    int minDiff = INT_MAX; // Initialize minimum difference to maximum integer value
    int minIndex = -1; // Initialize index for the minimum difference

    // Iterate through each index to calculate averages
    for (int i = 0; i < n; i++) {
        leftSum += nums[i]; // Update the left sum by adding the current element
        rightSum = totalSum - leftSum; // Calculate the right sum as total sum minus left sum
        
        int leftCount = i + 1; // Count of elements in the left part (i + 1)
        int rightCount = n - leftCount; // Count of elements in the right part (n - (i + 1))

        // Calculate left average
        long long leftAverage = leftSum / leftCount;
        // Calculate right average, set to 0 if it's the last element
        long long rightAverage = (i == n - 1) ? 0 : rightSum / rightCount;

        // Calculate the absolute difference between the two averages
        int difference = abs(leftAverage - rightAverage);
        
        // Update the minimum difference and index if a new minimum is found
        if (minDiff > difference) {
            minDiff = difference; // Update the minimum difference
            minIndex = i; // Update the index for minimum difference
        }
    }
    
    return minIndex; // Return the index with the minimum average difference
}

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)