Problem Description
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.
Key Insights
- The average of the first i + 1 elements can be calculated using a prefix sum approach.
- The average of the last n - i - 1 elements can also be derived from the total sum and the prefix sum.
- Special care is needed for edge cases where the last segment has zero elements (i.e., when i = n - 1).
- We need to compute the absolute difference for each index efficiently to find the minimum.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve this problem, we use a prefix sum array to compute the sum of the first i + 1 elements and derive the sum of the last n - i - 1 elements from the total sum of the array. We iterate through the array once, calculating the average difference for each index and keeping track of the minimum average difference and its corresponding index.