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:
n elements is the sum of the n elements divided (integer division) by n.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 <= 1050 <= nums[i] <= 105The idea is to use prefix sums to efficiently calculate the sum of elements up to any index and from any index to the end.
First, compute the prefix sum of the array. Use this prefix sum to calculate the sum of the first i+1 elements and the sum of the last n-i-1 elements. The prefixed sums allow these sums to be computed in constant time. For the entire array, calculate the absolute difference in averages at each index, keep track of the minimum difference, and return its index.
This solution uses two loops: one for calculating the total sum of the array and the other for calculating the minimum average difference by using prefix sums. The prefix sums allow for a constant time calculation of the first i+1 elements and the last n-i-1 elements at each step.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, since we iterate through the array twice.
Space Complexity: O(1), no extra space is used apart from variables to store sums.
This approach involves calculating total sum ahead of time and using a running sum in-place as we iterate through the array, allowing avoidance of additional space for prefix sums.
By subtracting the running sum from the total sum, we derive the right sum efficiently. Use these sums to calculate averages and determine minimal average difference efficiently.
In this approach, instead of explicitly creating a prefix sum array, we modify the running total inline during the loop, making it both time- and space-efficient.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Prefix Sum Technique | Time Complexity: O(n), where n is the length of the array, since we iterate through the array twice. |
| In-place Running Sums | Time Complexity: O(n) |
Minimum Difference Between Highest and Lowest of K Scores - Leetcode Weekly Contest - 1984 Python • NeetCode • 19,321 views views
Watch 9 more video solutions →Practice Minimum Average Difference with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor