Minimum Average of Smallest and Largest Elements

Difficulty: Easy | Acceptance: 85.30% | Paid: No Topics: Array, Two Pointers, Sorting

You are given an array nums consisting of positive integers.

Return the minimum possible average after removing the smallest and largest elements from the array repeatedly.

The average of k elements is the sum of the k elements divided by k.

Note that when you remove the largest and smallest elements, there may be multiple elements with the same value. You may remove any one instance.

Table of Contents

• Examples
• Constraints
• Sorting + Two Pointers
• Simulation (Brute Force)

Examples

Example 1:

Input: nums = [1,2,3,7,8,9] Output: 5.0 Explanation:

• Remove 1 and 9, average is (1 + 9) / 2 = 5.0.
• Remove 2 and 8, average is (2 + 8) / 2 = 5.0.
• Remove 3 and 7, average is (3 + 7) / 2 = 5.0. The minimum average is 5.0.

Example 2:

Input: nums = [1,2,3,4,5,6,7,8] Output: 4.5 Explanation:

• Remove 1 and 8, average is (1 + 8) / 2 = 4.5.
• Remove 2 and 7, average is (2 + 7) / 2 = 4.5.
• Remove 3 and 6, average is (3 + 6) / 2 = 4.5.
• Remove 4 and 5, average is (4 + 5) / 2 = 4.5. The minimum average is 4.5.

Example 3:

Input: nums = [1,2,3,4,5,6] Output: 3.5 Explanation:

• Remove 1 and 6, average is (1 + 6) / 2 = 3.5.
• Remove 2 and 5, average is (2 + 5) / 2 = 3.5.
• Remove 3 and 4, average is (3 + 4) / 2 = 3.5. The minimum average is 3.5.

Constraints

2 <= nums.length <= 50
nums.length is even.
1 <= nums[i] <= 50

Sorting + Two Pointers

Intuition If we sort the array, the smallest element will be at the beginning and the largest at the end. The pairs we form will always be the current smallest and current largest remaining elements. By sorting once, we can easily access these pairs using two pointers moving towards the center.

Steps

• Sort the array nums in ascending order.
• Initialize two pointers, left at 0 and right at nums.length - 1.
• Initialize min_avg to a large value (e.g., infinity).
• Iterate while left < right:
  • Calculate the average of nums[left] and nums[right].
  • Update min_avg if the current average is smaller.
  • Increment left and decrement right.
• Return min_avg.

class Solution:
    def minimumAverage(self, nums: list[int]) -> float:
        nums.sort()
        n = len(nums)
        min_avg = float('inf')
        for i in range(n // 2):
            avg = (nums[i] + nums[n - 1 - i]) / 2
            if avg < min_avg:
                min_avg = avg
        return min_avg

Complexity

• Time: O(N log N) due to sorting.
• Space: O(1) or O(N) depending on the sorting algorithm’s space complexity.
• Notes: This is the most efficient approach for this problem.

Simulation (Brute Force)

Intuition We can simulate the process exactly as described. In each step, find the minimum and maximum elements in the current array, calculate their average, and remove them from the array. Repeat until the array is empty.

Steps

• Initialize min_avg to infinity.
• Loop while nums is not empty:
  • Find the minimum value min_val and its index.
  • Find the maximum value max_val and its index.
  • Calculate the average of min_val and max_val.
  • Update min_avg if the current average is smaller.
  • Remove min_val and max_val from the array.
• Return min_avg.

class Solution:
    def minimumAverage(self, nums: list[int]) -> float:
        min_avg = float('inf')
        while nums:
            min_val = min(nums)
            max_val = max(nums)
            avg = (min_val + max_val) / 2
            if avg < min_avg:
                min_avg = avg
            nums.remove(min_val)
            nums.remove(max_val)
        return min_avg

Complexity

• Time: O(N²) because finding min/max and removing elements are O(N) operations, repeated N/2 times.
• Space: O(N) to store the list (if not in-place) or O(1) if modifying in-place (though removals are costly).
• Notes: This approach is less efficient than sorting but directly follows the problem description.