Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

Solution

Method 1 – Sorting and Two Pointers

Intuition

The smallest and largest elements can be efficiently found by sorting the array. By pairing the smallest and largest, then moving inward, we ensure each average is calculated correctly. The minimum of these averages is the answer.

Approach

  1. Sort the array nums in ascending order.
  2. Use two pointers: one at the start (l), one at the end (r).
  3. For each step, calculate the average of nums[l] and nums[r], add to averages.
  4. Move l forward and r backward, repeat until all pairs are processed.
  5. Return the minimum value in averages.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.size() - 1;
        double ans = DBL_MAX;
        while (l < r) {
            double avg = (nums[l] + nums[r]) / 2.0;
            ans = min(ans, avg);
            l++;
            r--;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func minimumAverage(nums []int) float64 {
    sort.Ints(nums)
    l, r := 0, len(nums)-1
    ans := math.MaxFloat64
    for l < r {
        avg := float64(nums[l]+nums[r]) / 2.0
        if avg < ans {
            ans = avg
        }
        l++
        r--
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public double minimumAverage(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        double ans = Double.MAX_VALUE;
        while (l < r) {
            double avg = (nums[l] + nums[r]) / 2.0;
            ans = Math.min(ans, avg);
            l++;
            r--;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minimumAverage(nums: IntArray): Double {
        nums.sort()
        var l = 0
        var r = nums.size - 1
        var ans = Double.MAX_VALUE
        while (l < r) {
            val avg = (nums[l] + nums[r]) / 2.0
            ans = minOf(ans, avg)
            l++
            r--
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def minimum_average(nums: list[int]) -> float:
    nums.sort()
    l, r = 0, len(nums) - 1
    ans: float = float('inf')
    while l < r:
        avg = (nums[l] + nums[r]) / 2.0
        ans = min(ans, avg)
        l += 1
        r -= 1
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn minimum_average(nums: Vec<i32>) -> f64 {
        let mut nums = nums;
        nums.sort();
        let (mut l, mut r) = (0, nums.len() - 1);
        let mut ans = f64::INFINITY;
        while l < r {
            let avg = (nums[l] + nums[r]) as f64 / 2.0;
            if avg < ans {
                ans = avg;
            }
            l += 1;
            r -= 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minimumAverage(nums: number[]): number {
        nums.sort((a, b) => a - b);
        let l = 0, r = nums.length - 1;
        let ans = Number.POSITIVE_INFINITY;
        while (l < r) {
            const avg = (nums[l] + nums[r]) / 2;
            ans = Math.min(ans, avg);
            l++;
            r--;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting the array of size n.
  • 🧺 Space complexity: O(1), as only a few variables are used for pointers and answer.