We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Average Difference

Number: 2342

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a 0-indexed integer array nums, the task is to find an index i that minimizes the absolute difference between the average of the first i+1 elements and the average of the remaining n-i-1 elements. Both averages are computed using integer division (rounded down). If the index is the last element, the second average is considered 0. If there are multiple indices with the same minimum difference, return the smallest index.

Key Insights

  • Use prefix sums to efficiently compute the sum of the subarrays.
  • At each index, maintain a running sum to calculate the left part average.
  • For the right part, use the total sum minus the current prefix sum.
  • Carefully handle the case when there are no elements on the right by considering their average as 0.
  • Iterate through the array once, leading to an optimal O(n) solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (ignoring the input storage)

Solution

The approach begins by computing the total sum of the array. As you iterate over the elements, maintain a running prefix sum. At each index, compute:

  • left_average = prefix_sum / (i + 1) (using integer division)
  • right_average = (total_sum - prefix_sum) / (n - i - 1) (if i is not the last index; otherwise, it is 0) Calculate the absolute difference between left_average and right_average and track the minimum difference encountered along with the corresponding index. Finally, return the index with the minimum average difference.

Code Solutions

def minimumAverageDifference(nums):
    n = len(nums)
    total_sum = sum(nums)  # Total sum of the array
    prefix_sum = 0  # Running prefix sum
    min_diff = float('inf')  # Initialize minimum difference to infinity
    min_index = -1  # To store the index with minimum average difference
    
    for i in range(n):
        prefix_sum += nums[i]  # Update the prefix sum for index i
        left_avg = prefix_sum // (i + 1)  # Calculate left average using integer division
        
        # Calculate right average; if no elements remain, use 0
        if i < n - 1:
            right_avg = (total_sum - prefix_sum) // (n - i - 1)
        else:
            right_avg = 0
        
        # Calculate the absolute difference between the two averages
        diff = abs(left_avg - right_avg)
        
        # Update minimum difference and index if needed
        if diff < min_diff:
            min_diff = diff
            min_index = i
            
    return min_index

# Example usage:
# print(minimumAverageDifference([2,5,3,9,5,3]))
← Back to All Questions