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 of Smallest and Largest Elements

Number: 3471

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an even-length array of integers called nums, repeatedly remove the smallest and largest elements from nums and compute their average. Append each computed average to an initially empty array called averages. After performing this procedure n/2 times (where n is the length of nums), return the minimum value among all the averages.

Key Insights

  • Sorting the array makes it easy to consistently retrieve the smallest and largest available elements.
  • After sorting, the smallest element is at the beginning and the largest at the end.
  • Pairing the ith smallest with the ith largest (using two pointers) directly simulates the removal process.
  • The solution then involves computing averages for these pairs and determining the minimum average.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) extra space if sorting is done in-place (or O(n) if extra space is used for the sorted copy).

Solution

The algorithm starts by sorting the input array. Two pointers (one starting at the beginning and the other at the end of the array) are then used to form pairs of the smallest and largest elements that remain. For each pair, the average is computed and tracked if it is the smallest average seen so far. Finally, the minimum average is returned. This approach avoids the overhead of repeatedly removing elements from the array, thus optimizing the process.

Code Solutions

def minimum_average(nums):
    # Sort the array to allow pairing smallest and largest elements directly.
    nums.sort()
    n = len(nums)
    min_avg = float('inf')
    
    # Use two pointers to form pairs from the sorted array.
    for i in range(n // 2):
        # Calculate the average of the current pair.
        avg = (nums[i] + nums[n - 1 - i]) / 2
        # Keep track of the minimum average.
        min_avg = min(min_avg, avg)
        
    return min_avg

# Example usage:
print(minimum_average([7, 8, 3, 4, 15, 13, 4, 1]))
← Back to All Questions