Minimum Average Difference

Problem Description

Given a 0-indexed integer array nums of length n, the average difference of index i is the absolute difference between the average of the first i + 1 elements and the average of the last n - i - 1 elements. Both averages are rounded down to the nearest integer. The goal is to find the index with the minimum average difference. If multiple indices have the minimum average difference, return the smallest one.

Solution Approach

The optimal approach involves a single pass through the array using prefix sums to efficiently calculate the averages. This avoids redundant calculations and leads to a linear time complexity solution.

1. Calculate Total Sum: First, calculate the total sum of all elements in nums. This will be used later for calculating the sum of the last n - i - 1 elements.

2. Iterate and Calculate Averages: Iterate through the array. For each index i:

   • Calculate the sum of the first i + 1 elements (prefixSum).
   • Calculate the sum of the last n - i - 1 elements (suffixSum) using the total sum and the prefixSum.
   • Calculate the average of the first i + 1 elements (avg1). Handle the edge case where i + 1 is 0 to avoid division by zero.
   • Calculate the average of the last n - i - 1 elements (avg2). Handle the edge case where n - i - 1 is 0.
   • Compute the absolute difference between avg1 and avg2.
   • Update the minimum average difference (minDiff) and the corresponding index (minIndex) if a smaller difference is found.

3. Return Minimum Index: After iterating through all indices, return minIndex, which holds the index with the minimum average difference.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array nums. We perform a single pass through the array.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size.

Code Implementation (Python)

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = sum(nums)
        min_diff = float('inf')
        min_index = 0
        prefix_sum = 0
 
        for i in range(n):
            prefix_sum += nums[i]
            avg1 = prefix_sum // (i + 1) if i + 1 > 0 else 0
            avg2 = (total_sum - prefix_sum) // (n - i - 1) if n - i - 1 > 0 else 0
            diff = abs(avg1 - avg2)
 
            if diff < min_diff:
                min_diff = diff
                min_index = i
 
        return min_index
 

Code Implementation (Java)

class Solution {
    public int minimumAverageDifference(int[] nums) {
        int n = nums.length;
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        long minDiff = Long.MAX_VALUE;
        int minIndex = 0;
        long prefixSum = 0;
 
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            long avg1 = (i + 1) == 0 ? 0 : prefixSum / (i + 1);
            long avg2 = (n - i - 1) == 0 ? 0 : (totalSum - prefixSum) / (n - i - 1);
            long diff = Math.abs(avg1 - avg2);
 
            if (diff < minDiff) {
                minDiff = diff;
                minIndex = i;
            }
        }
        return minIndex;
    }
}

Code Implementation (C++)

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        int n = nums.size();
        long long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        long long minDiff = LLONG_MAX;
        int minIndex = 0;
        long long prefixSum = 0;
 
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            long long avg1 = (i + 1) == 0 ? 0 : prefixSum / (i + 1);
            long long avg2 = (n - i - 1) == 0 ? 0 : (totalSum - prefixSum) / (n - i - 1);
            long long diff = abs(avg1 - avg2);
 
            if (diff < minDiff) {
                minDiff = diff;
                minIndex = i;
            }
        }
        return minIndex;
    }
};

The code implementations in other languages (JavaScript, Go, etc.) would follow a similar structure, adapting the syntax and data types as needed. The core logic remains the same, leveraging prefix sums for efficient average calculations.