#2256

Medium

LeetCode Problem Workspace

Minimum Average Difference

Find the index with the minimum average difference in an array using prefix sums.

Problem Statement

You are 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 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.

Examples

Example 1

Input: nums = [2,5,3,9,5,3]

Output: 3

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

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 <= 105
0 <= nums[i] <= 105

Solution Approach

Precompute prefix sums

We first compute a prefix sum array to store the cumulative sum of elements up to each index. This allows for efficient computation of the average of the first i + 1 elements at any index.

Calculate average difference

At each index, calculate the average difference between the first and second part of the array. Use the precomputed prefix sums to quickly determine the sums and averages of both parts.

Minimize average difference

Iterate through all indices and track the index with the smallest average difference. If there are multiple indices with the same minimum, return the smallest index.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n) due to the single pass for calculating prefix sums and another pass for determining the minimum average difference. The space complexity is also O(n) because of the storage required for the prefix sum array.

What Interviewers Usually Probe

Can the candidate optimize the problem using prefix sums?
Is the candidate able to think about precalculation and its benefits?
Does the candidate consider edge cases, like arrays with a single element?

Common Pitfalls or Variants

Common pitfalls

Not using prefix sums to optimize the calculation of averages.
Recalculating sums repeatedly instead of leveraging precomputed values.
Failing to handle arrays with a single element, which should return 0 immediately.

Follow-up variants

What if the array contains only one element?
How would the solution change if negative numbers are allowed in the array?
Can we optimize further for very large arrays?

FAQ

What is the Minimum Average Difference problem?

The Minimum Average Difference problem asks to find the index with the minimum absolute difference between the average of the first and second parts of the array, using efficient methods like prefix sums.

How do prefix sums help in solving this problem?

Prefix sums allow for quick calculation of cumulative sums, which helps in efficiently determining the averages for the first and second parts of the array at each index.

What is the time complexity of solving the Minimum Average Difference problem?

The time complexity is O(n) because we compute the prefix sums once and then perform another pass through the array to calculate and compare the average differences.

How should I handle arrays with only one element?

If the array has only one element, the answer is trivially index 0, as there's no other element to compare averages with.

Can this problem be solved without using prefix sums?

While it is possible to solve the problem without prefix sums, it would require recalculating sums for each index, resulting in a less efficient O(n^2) time complexity.

terminal

Solution

Solution 1: Traverse

We directly traverse the array $nums$. For each index $i$, we maintain the sum of the first $i+1$ elements $pre$ and the sum of the last $n-i-1$ elements $suf$. We calculate the absolute difference of the average of the first $i+1$ elements and the average of the last $n-i-1$ elements, denoted as $t$. If $t$ is less than the current minimum value $mi$, we update the answer $ans=i$ and the minimum value $mi=t$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        pre, suf = 0, sum(nums)
        n = len(nums)
        ans, mi = 0, inf
        for i, x in enumerate(nums):
            pre += x
            suf -= x
            a = pre // (i + 1)
            b = 0 if n - i - 1 == 0 else suf // (n - i - 1)
            if (t := abs(a - b)) < mi:
                ans = i
                mi = t
        return ans

Continue Practicing

#2251 number of flowers in full bloom #2245 maximum trailing zeros in a cornered path #2270 number of ways to split array