# Minimum Average of Smallest and Largest Elements
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-average-of-smallest-and-largest-elements)
Canonical: https://scaleengineer.com/dsa/problems/minimum-average-of-smallest-and-largest-elements
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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`.

**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
## Brute-Force Simulation
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.
**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`.
**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.
### Explanation
```java
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;
    }
}
```
### 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`.

## Sorting and Two Pointers
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.
**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)`.
**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.
### Explanation
```java
import java.util.Arrays;

class Solution {
    public double minimumAverage(int[] nums) {
        Arrays.sort(nums);
        double minAverage = Double.MAX_VALUE;
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            double currentAverage = (nums[left] + nums[right]) / 2.0;
            minAverage = Math.min(minAverage, currentAverage);
            left++;
            right--;
        }

        return minAverage;
    }
}
```
### 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`.

## Counting Sort and Two Pointers
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.
**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.
**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.
### Explanation
```java
class Solution {
    public double minimumAverage(int[] nums) {
        int[] counts = new int[51]; // For numbers 1 to 50
        for (int num : nums) {
            counts[num]++;
        }

        double minAverage = Double.MAX_VALUE;
        int minVal = 1;
        int maxVal = 50;
        int n = nums.length;
        int pairs = 0;

        while (pairs < n / 2) {
            // Find the smallest available number
            while (counts[minVal] == 0) {
                minVal++;
            }
            // Find the largest available number
            while (counts[maxVal] == 0) {
                maxVal--;
            }

            // Calculate average and update minAverage
            double currentAverage = (minVal + maxVal) / 2.0;
            minAverage = Math.min(minAverage, currentAverage);

            // "Remove" the elements by decrementing their counts
            counts[minVal]--;
            counts[maxVal]--;
            
            pairs++;
        }

        return minAverage;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double minimumAverage(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int ans = 1 << 30, n = nums.size();
    for (int i = 0; i < n; ++i) {
      ans = min(ans, nums[i] + nums[n - i - 1]);
    }
    return ans / 2.0;
  }
};

```

### Python

```python
class Solution:
    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

```