Scale Engineer

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

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public double minimumAverage(int[] nums) {        List<Integer> list = new ArrayList<>();        for (int num : nums) {            list.add(num);        }         double minAverage = Double.MAX_VALUE;        int n = nums.length;         for (int i = 0; i < n / 2; i++) {            int minElement = Collections.min(list);            int maxElement = Collections.max(list);             double currentAverage = (minElement + maxElement) / 2.0;            minAverage = Math.min(minAverage, currentAverage);             // Remove one occurrence of minElement and maxElement            list.remove(Integer.valueOf(minElement));            list.remove(Integer.valueOf(maxElement));        }         return minAverage;    }}

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.

Solutions

class Solution {public  double minimumAverage(int[] nums) {    Arrays.sort(nums);    int n = nums.length;    int ans = 1 << 30;    for (int i = 0; i < n / 2; ++i) {      ans = Math.min(ans, nums[i] + nums[n - i - 1]);    }    return ans / 2.0;  }}

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 →

Next problem