🌱 Keegan's Digital Garden

2256. Minimum Average Difference

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

The problem can be approached using prefix sums to calculate the averages for the left and right parts of the array efficiently. 
The main idea is to minimize the absolute difference between these averages for every index. 
Iterating through the array and using a cumulative sum would ensure an O(n) solution.

🤔What Did I Struggle With?

- understanding how prefix and postfix integrate into solving the problem
- integer overflow when summing up to large values in the array

💡 Explanation of Solution

1. Calculate the total sum of the array

2. Traverse the array while maintaining a prefix sum (`prefixSum`), which is the sum of elements from the start to the current index.

3. At each index `i`:
   - Calculate the average of the left part as `prefixSum / (i + 1)`.
   - Calculate the average of the right part as `(totalSum - prefixSum) / (n - i - 1)`, with special handling when the right part is empty.

4. Compute the absolute difference between these two averages and keep track of the minimum difference and its corresponding index.

5. Return the index where the minimum average difference occurs.

⌛ Complexity Analysis

Time Complexity: O(n)
- linear iteration to compute the total sum of the array values
- linear iteration to find the minimum difference and compute prefix / suffix values

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        // Calculate totalSum of the array
        long totalSum = accumulate(begin(nums), end(nums), 0L, plus<long>());
 
        long prefixSum = 0;
        int n = nums.size();
        int minDifference = INT_MAX;
        int resultIndex = 0;
 
        // Traverse the array to calculate averages and find the minimum difference
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
 
            // Average of the first i+1 elements
            int leftAverage = prefixSum / (i + 1);
 
            // Handle the right average for the remaining elements
            int rightAverage = (i == n - 1) ? 0 : (totalSum - prefixSum) / (n - i - 1);
 
            // Calculate the absolute difference
            int currentDifference = abs(leftAverage - rightAverage);
 
            // Update minimum difference and the corresponding index
            if (currentDifference < minDifference) {
                minDifference = currentDifference;
                resultIndex = i;
            }
        }
        return resultIndex;
    }
};

Graph View