LeetCode 2256 - Minimum Average Difference

In this problem, we are given a 0-indexed integer array nums, and for every index i, we must compute something called the "average difference".

leetcodemediumarrayprefix-sum

LeetCode Problem 2256

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

In this problem, we are given a 0-indexed integer array nums, and for every index i, we must compute something called the "average difference".

For a particular index i, the array is split into two parts:

  • The left part contains elements from index 0 through i
  • The right part contains elements from index i + 1 through the end of the array

We then compute:

  1. The average of the left part
  2. The average of the right part
  3. The absolute difference between those two averages

All averages use integer division, meaning the result is rounded down automatically.

The goal is to return the index whose average difference is the smallest. If multiple indices produce the same minimum difference, we must return the smallest index among them.

The input array can contain up to 10^5 elements, and each value can also be as large as 10^5. These constraints are important because they immediately rule out inefficient repeated-summation approaches. Any solution that repeatedly scans subarrays for every index will become too slow.

Another important detail is that the average of zero elements is defined as 0. This matters when i is the last index in the array, because the right side becomes empty.

For example:

  • If i = n - 1
  • Left side contains the whole array
  • Right side contains zero elements
  • Right average must therefore be treated as 0

Several edge cases are important:

  • Arrays with only one element
  • Arrays where all values are identical
  • Arrays where the minimum difference occurs multiple times
  • Large arrays that require efficient processing
  • Handling division carefully with integer truncation

The problem guarantees:

  • The array always contains at least one element
  • All numbers are non-negative integers

These guarantees simplify handling because we never need to deal with negative sums or empty input arrays.

Approaches

Brute Force Approach

The most straightforward solution is to compute the average difference independently for every index.

For each position i:

  1. Compute the sum of the left subarray nums[0:i+1]
  2. Compute the sum of the right subarray nums[i+1:n]
  3. Compute both averages
  4. Compute their absolute difference
  5. Track the minimum difference and corresponding index

This approach is correct because it directly follows the definition of the problem.

However, it is inefficient. Computing subarray sums repeatedly causes a large amount of redundant work. For each index, we potentially scan most of the array again.

If the array has n elements:

  • There are n indices
  • Each index may require O(n) work to compute sums

This leads to O(n^2) time complexity, which is too slow for n = 10^5.

Optimal Approach Using Prefix Sums

The key observation is that we do not need to recompute sums repeatedly.

If we know:

  • The total sum of the array
  • The running prefix sum while iterating

Then we can compute:

  • Left sum instantly from the prefix sum
  • Right sum as totalSum - leftSum

This eliminates repeated scanning entirely.

At each index:

  • Left average = leftSum // leftCount
  • Right average = rightSum // rightCount
  • If the right side is empty, right average is 0

Because each index is processed exactly once, the solution becomes linear.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Recomputes subarray sums repeatedly
Optimal O(n) O(1) Uses running prefix sums and total sum

Algorithm Walkthrough

  1. Compute the total sum of the entire array.

This allows us to derive the right-side sum at any index without rescanning the array. 2. Initialize variables:

  • prefixSum = 0
  • minimumDifference = infinity
  • answerIndex = 0

The prefix sum will track the cumulative sum of the left side as we iterate. 3. Iterate through the array from left to right.

For each index i:

  • Add nums[i] to prefixSum
  • Compute the left-side average using:

leftAverage = prefixSum // (i + 1) 4. Compute the right-side sum.

Since we already know the total array sum:

rightSum = totalSum - prefixSum 5. Compute the right-side average.

The number of elements on the right side is:

rightCount = n - i - 1

If rightCount > 0:

rightAverage = rightSum // rightCount

Otherwise:

rightAverage = 0 6. Compute the absolute difference.

difference = abs(leftAverage - rightAverage) 7. Update the answer if necessary.

If the current difference is smaller than the best seen so far:

  • Update minimumDifference
  • Store the current index

Since we only update on strictly smaller differences, ties automatically preserve the smallest index. 8. Continue until all indices are processed. 9. Return the stored answer index.

Why it works

The algorithm works because every index is evaluated exactly according to the problem definition.

The prefix sum invariant guarantees that after processing index i, prefixSum equals the sum of elements from 0 through i. Since the total sum is fixed, subtracting the prefix sum always produces the correct right-side sum.

Every average difference is therefore computed correctly, and by keeping track of the smallest difference encountered, the algorithm eventually returns the correct index.

Python Solution

from typing import List

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        prefix_sum = 0

        minimum_difference = float("inf")
        answer_index = 0

        n = len(nums)

        for i in range(n):
            prefix_sum += nums[i]

            left_average = prefix_sum // (i + 1)

            right_count = n - i - 1
            right_sum = total_sum - prefix_sum

            if right_count > 0:
                right_average = right_sum // right_count
            else:
                right_average = 0

            difference = abs(left_average - right_average)

            if difference < minimum_difference:
                minimum_difference = difference
                answer_index = i

        return answer_index

The implementation begins by computing the total sum of the array. This is essential because it allows the right-side sum to be computed in constant time during iteration.

The variable prefix_sum tracks the cumulative sum of the left portion of the array. As we iterate through each index, the current value is added into this running sum.

For every index:

  • The left average is computed using the prefix sum
  • The right sum is derived from total_sum - prefix_sum
  • The right average is computed carefully, with special handling for an empty right side

The absolute difference between the two averages is then calculated.

Whenever a smaller difference is found, the algorithm updates both the minimum difference and the answer index.

Because the loop processes each element exactly once, the solution runs efficiently in linear time.

Go Solution

package main

import "math"

func minimumAverageDifference(nums []int) int {
	n := len(nums)

	totalSum := 0
	for _, num := range nums {
		totalSum += num
	}

	prefixSum := 0
	minDifference := math.MaxInt64
	answerIndex := 0

	for i := 0; i < n; i++ {
		prefixSum += nums[i]

		leftAverage := prefixSum / (i + 1)

		rightCount := n - i - 1
		rightSum := totalSum - prefixSum

		rightAverage := 0
		if rightCount > 0 {
			rightAverage = rightSum / rightCount
		}

		difference := leftAverage - rightAverage
		if difference < 0 {
			difference = -difference
		}

		if difference < minDifference {
			minDifference = difference
			answerIndex = i
		}
	}

	return answerIndex
}

The Go implementation follows the same logic as the Python solution, but there are some language-specific considerations.

Go does not provide a built-in absolute value function for integers in the same way Python does, so the code manually converts negative differences into positive values.

The variable minDifference is initialized using math.MaxInt64 to ensure that any valid computed difference will be smaller during the first comparison.

Go integer division automatically truncates toward zero, which matches the problem's requirement for floor division because all numbers are non-negative.

The implementation also avoids extra memory allocations by using only scalar variables.

Worked Examples

Example 1

Input:

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

Initial values:

totalSum = 27
i prefixSum leftAverage rightSum rightCount rightAverage difference bestIndex
0 2 2 25 5 5 3 0
1 7 3 20 4 5 2 1
2 10 3 17 3 5 2 1
3 19 4 8 2 4 0 3
4 24 4 3 1 3 1 3
5 27 4 0 0 0 4 3

The minimum difference is 0, which occurs at index 3.

Final answer:

3

Example 2

Input:

nums = [0]

Initial values:

totalSum = 0
i prefixSum leftAverage rightSum rightCount rightAverage difference bestIndex
0 0 0 0 0 0 0 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed exactly once
Space O(1) Only a constant number of variables are used

The algorithm performs a single pass through the array. Every operation inside the loop is constant time, so the overall running time grows linearly with the input size.

The solution uses only a few integer variables regardless of input size, so the auxiliary space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        prefix_sum = 0

        minimum_difference = float("inf")
        answer_index = 0

        n = len(nums)

        for i in range(n):
            prefix_sum += nums[i]

            left_average = prefix_sum // (i + 1)

            right_count = n - i - 1
            right_sum = total_sum - prefix_sum

            if right_count > 0:
                right_average = right_sum // right_count
            else:
                right_average = 0

            difference = abs(left_average - right_average)

            if difference < minimum_difference:
                minimum_difference = difference
                answer_index = i

        return answer_index

solution = Solution()

assert solution.minimumAverageDifference([2,5,3,9,5,3]) == 3
# Provided example with minimum in middle

assert solution.minimumAverageDifference([0]) == 0
# Single element array

assert solution.minimumAverageDifference([1,1,1,1]) == 0
# Multiple equal minimum differences, choose smallest index

assert solution.minimumAverageDifference([10,20,30,40,50]) == 0
# Minimum occurs at beginning

assert solution.minimumAverageDifference([1,2,3,4,5,6]) == 3
# Increasing sequence

assert solution.minimumAverageDifference([100000]) == 0
# Maximum single value

assert solution.minimumAverageDifference([0,0,0,0]) == 0
# All zeros

assert solution.minimumAverageDifference([5,5,5,5,5]) == 0
# Uniform values

assert solution.minimumAverageDifference([1,100000,1,100000,1]) == 0
# Large value fluctuations

assert solution.minimumAverageDifference([8,1,2,3,9]) == 2
# General mixed values
Test Why
[2,5,3,9,5,3] Validates the primary example
[0] Tests single-element edge case
[1,1,1,1] Ensures smallest index is returned on ties
[10,20,30,40,50] Tests minimum at the beginning
[1,2,3,4,5,6] Tests normal increasing sequence
[100000] Tests maximum allowed value
[0,0,0,0] Tests all-zero handling
[5,5,5,5,5] Tests identical values
[1,100000,1,100000,1] Tests large fluctuations
[8,1,2,3,9] Tests general mixed input

Edge Cases

Single Element Array

An array with only one element is an important edge case because the right side becomes empty immediately.

For example:

[7]

At index 0:

  • Left average is 7
  • Right average must be treated as 0

A common bug is attempting to divide by zero when computing the right-side average. The implementation avoids this by explicitly checking whether the right-side count is zero.

Multiple Minimum Differences

It is possible for several indices to produce the same minimum average difference.

For example:

[1,1,1,1]

Every index may produce the same difference value.

The problem requires returning the smallest index in such cases. The implementation handles this correctly by only updating the answer when a strictly smaller difference is found. Equal differences do not overwrite the earlier index.

Last Index Handling

When processing the final index:

  • The left side contains the entire array
  • The right side contains zero elements

This case is particularly easy to mishandle because the right-side denominator becomes zero.

The implementation safely handles this scenario using:

if right_count > 0:
    right_average = right_sum // right_count
else:
    right_average = 0

This directly follows the problem definition and prevents division errors.