Minimum Average of Smallest and Largest Elements

Easy

#2837Time: O(n^2). The main loop runs `n/2` times. Inside the loop, finding the min and max elements takes `O(k)` time, where `k` is the current size of the list. Removing an element from an `ArrayList` also takes `O(k)`. Since `k` decreases from `n` down to 2, the total time complexity is a sum of an arithmetic series, resulting in `O(n^2)`.Space: O(n). We use an `ArrayList` to store a copy of the numbers, which requires space proportional to the input size `n`.

Patterns

Two Pointers

Algorithms

Sorting

Data structures

Array

Prompt

You have an array of floating point numbers averages which is initially empty. You are given an array nums of n integers where n is even.

You repeat the following procedure n / 2 times:

Remove the smallest element, minElement, and the largest element maxElement, from nums.
Add (minElement + maxElement) / 2 to averages.

Return the minimum element in averages.

Example 1:

Input: nums = [7,8,3,4,15,13,4,1]

Output: 5.5

Explanation:

step	nums	averages
0	[7,8,3,4,15,13,4,1]	[]
1	[7,8,3,4,13,4]	[8]
2	[7,8,4,4]	[8,8]
3	[7,4]	[8,8,6]
4	[]	[8,8,6,5.5]

The smallest element of averages, 5.5, is returned.

Example 2:

Input: nums = [1,9,8,3,10,5]

Output: 5.5

Explanation:

step	nums	averages
0	[1,9,8,3,10,5]	[]
1	[9,8,3,5]	[5.5]
2	[8,5]	[5.5,6]
3	[]	[5.5,6,6.5]

Example 3:

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

Output: 5.0

Explanation:

step	nums	averages
0	[1,2,3,7,8,9]	[]
1	[2,3,7,8]	[5]
2	[3,7]	[5,5]
3	[]	[5,5,5]

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We use a data structure that allows for dynamic resizing and element removal, such as an ArrayList. In each step, we iterate through the current list to find the minimum and maximum elements, calculate their average, and then remove them. We repeat this process until the list is empty, keeping track of the minimum average found.

Algorithm

Convert the input array nums into a List<Integer> to facilitate easy element removal.
Initialize a variable minAverage to Double.MAX_VALUE.
Loop n / 2 times, where n is the initial size of nums.
In each iteration:
- Find the minimum (minElement) and maximum (maxElement) values in the current list. This can be done by iterating through the list or using Collections.min() and Collections.max().
- Calculate the average: currentAverage = (minElement + maxElement) / 2.0.
- Update minAverage = Math.min(minAverage, currentAverage).
- Remove the minElement and maxElement from the list. Note that removing by value requires careful handling, especially if there are duplicates. It's safer to remove by index or use list.remove(Integer.valueOf(value)).
After the loop completes, return minAverage.

Walkthrough

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public double minimumAverage(int[] nums) {7        List<Integer> list = new ArrayList<>();8        for (int num : nums) {9            list.add(num);10        }11 12        double minAverage = Double.MAX_VALUE;13        int n = nums.length;14 15        for (int i = 0; i < n / 2; i++) {16            int minElement = Collections.min(list);17            int maxElement = Collections.max(list);18 19            double currentAverage = (minElement + maxElement) / 2.0;20            minAverage = Math.min(minAverage, currentAverage);21 22            // Remove one occurrence of minElement and maxElement23            list.remove(Integer.valueOf(minElement));24            list.remove(Integer.valueOf(maxElement));25        }26 27        return minAverage;28    }29}

Complexity

Time

O(n^2). The main loop runs `n/2` times. Inside the loop, finding the min and max elements takes `O(k)` time, where `k` is the current size of the list. Removing an element from an `ArrayList` also takes `O(k)`. Since `k` decreases from `n` down to 2, the total time complexity is a sum of an arithmetic series, resulting in `O(n^2)`.

Space

O(n). We use an `ArrayList` to store a copy of the numbers, which requires space proportional to the input size `n`.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem statement.

Cons

Inefficient due to repeated searches for min/max and costly removal operations.

A more efficient approach involves sorting the array first. Once the array is sorted, the smallest element is always at the beginning and the largest is at the end. We can use two pointers, one starting from the left end (left) and one from the right end (right), to pair the smallest and largest elements, calculate their average, and then move the pointers inward. This avoids the costly search for min and max elements in each step.

Algorithm

Sort the input array nums in non-decreasing order.
Initialize a variable minAverage to Double.MAX_VALUE.
Initialize two pointers: left = 0 and right = nums.length - 1.
Loop while left < right.
In each iteration:
- The current smallest element is nums[left] and the largest is nums[right].
- Calculate their average: currentAverage = (nums[left] + nums[right]) / 2.0.
- Update minAverage = Math.min(minAverage, currentAverage).
- Move the pointers closer to the center: left++ and right--.
After the loop finishes, minAverage will hold the minimum average of all pairs. Return minAverage.

Walkthrough

1import java.util.Arrays;2 3class Solution {4    public double minimumAverage(int[] nums) {5        Arrays.sort(nums);6        double minAverage = Double.MAX_VALUE;7        int left = 0;8        int right = nums.length - 1;9 10        while (left < right) {11            double currentAverage = (nums[left] + nums[right]) / 2.0;12            minAverage = Math.min(minAverage, currentAverage);13            left++;14            right--;15        }16 17        return minAverage;18    }19}

Complexity

Time

O(n log n). The dominant operation is sorting the array. The subsequent two-pointer scan takes `O(n)` time.

Space

O(log n) or O(1). This depends on the implementation of the sorting algorithm. `Arrays.sort()` in Java for primitives has an average space complexity of `O(log n)` due to the recursion stack of Quicksort. If we ignore the stack space, it's considered `O(1)`.

Trade-offs

Pros

Significantly more efficient than the simulation approach.
The logic is clean and easy to follow after the initial insight about sorting.

Cons

The O(n log n) time complexity from sorting is the bottleneck, which can be improved upon given the problem's constraints.

This is the most optimal approach, leveraging the constraint that the numbers in nums are within a small, fixed range (1 to 50). We can use a frequency array (a simplified form of counting sort) to count the occurrences of each number. Then, we use two pointers, one scanning from the smallest possible value (1) upwards and the other from the largest (50) downwards on the frequency array to find the current minimum and maximum elements to pair up.

Algorithm

Create a frequency array, counts, of size 51 (indices 0-50) to store the counts of each number from 1 to 50. Initialize all counts to 0.
Iterate through the input nums array and populate the counts array: for each num, increment counts[num].
Initialize minAverage to Double.MAX_VALUE.
Initialize two pointers for the values: minVal = 1 and maxVal = 50.
Loop n / 2 times.
In each iteration:
- Find the current smallest available number by advancing minVal while counts[minVal] is 0.
- Find the current largest available number by decrementing maxVal while counts[maxVal] is 0.
- Calculate the average: currentAverage = (minVal + maxVal) / 2.0.
- Update minAverage = Math.min(minAverage, currentAverage).
- Decrement the counts for the used numbers: counts[minVal]-- and counts[maxVal]--.
Return minAverage.

Walkthrough

1class Solution {2    public double minimumAverage(int[] nums) {3        int[] counts = new int[51]; // For numbers 1 to 504        for (int num : nums) {5            counts[num]++;6        }7 8        double minAverage = Double.MAX_VALUE;9        int minVal = 1;10        int maxVal = 50;11        int n = nums.length;12        int pairs = 0;13 14        while (pairs < n / 2) {15            // Find the smallest available number16            while (counts[minVal] == 0) {17                minVal++;18            }19            // Find the largest available number20            while (counts[maxVal] == 0) {21                maxVal--;22            }23 24            // Calculate average and update minAverage25            double currentAverage = (minVal + maxVal) / 2.0;26            minAverage = Math.min(minAverage, currentAverage);27 28            // "Remove" the elements by decrementing their counts29            counts[minVal]--;30            counts[maxVal]--;31            32            pairs++;33        }34 35        return minAverage;36    }37}

Complexity

Time

O(n + k), where `n` is the number of elements and `k` is the range of values (51 in this case). `O(n)` to build the frequency map, and `O(k)` for the two pointers to scan the range. This is effectively linear time.

Space

O(k). We need an auxiliary array of size `k` (where k=51) to store the frequencies.

Trade-offs

Pros

Achieves linear time complexity, which is optimal.
Very efficient for inputs where the range of values is small compared to the number of elements.

Cons

The space complexity depends on the range of values (k), which might be large in other problems, making this approach less general.
Slightly more complex to implement than the standard sorting approach.

Solutions

Solution

1class Solution {2public3  double minimumAverage(int[] nums) {4    Arrays.sort(nums);5    int n = nums.length;6    int ans = 1 << 30;7    for (int i = 0; i < n / 2; ++i) {8      ans = Math.min(ans, nums[i] + nums[n - i - 1]);9    }10    return ans / 2.0;11  }12}

1class Solution {2public:3  double minimumAverage(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int ans = 1 << 30, n = nums.size();6    for (int i = 0; i < n; ++i) {7      ans = min(ans, nums[i] + nums[n - i - 1]);8    }9    return ans / 2.0;10  }11};

1class Solution:2    def minimumAverage(self, nums: List[int]) -> float: nums . sort() n = len(nums) return min(nums[i] + nums[n - i - 1] for i in range(n // 2)) / 2

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  double minimumAverage(int[] nums) {4    Arrays.sort(nums);5    int n = nums.length;6    int ans = 1 << 30;7    for (int i = 0; i < n / 2; ++i) {8      ans = Math.min(ans, nums[i] + nums[n - i - 1]);9    }10    return ans / 2.0;11  }12}

1class Solution {2public:3  double minimumAverage(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int ans = 1 << 30, n = nums.size();6    for (int i = 0; i < n; ++i) {7      ans = min(ans, nums[i] + nums[n - i - 1]);8    }9    return ans / 2.0;10  }11};

1class Solution:2    def minimumAverage(self, nums: List[int]) -> float: nums . sort() n = len(nums) return min(nums[i] + nums[n - i - 1] for i in range(n // 2)) / 2

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.