3194. Minimum Average of Smallest and Largest Elements

Problem Description

You are given an array of floating point numbers named averages, which starts as empty. You also have an array nums containing n integers, where n is an even number. The task is to perform the following procedure n/2 times:

Remove the smallest element, minElement, and the largest element, maxElement, from nums.
Calculate their average: (minElement + maxElement) / 2 and add this result to the averages array.

Finally, your goal is to return the smallest element from the averages array.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem efficiently, we can use the strategy of sorting the array nums. By sorting, the smallest and largest elements can be quickly accessed from the beginning and end of the array, respectively. This approach simplifies the process of repeatedly removing these elements. Once sorted, for each operation, pair the smallest unprocessed element with the largest. This ensures that each pair contributes to the averages systematically. The smallest average formed from these pairs will be the answer, which can be found after dividing each sum by 2 and choosing the minimum. This method leverages sorting to achieve a straightforward solution, reducing complexity while ensuring accuracy.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution uses the following steps:

Sorting: Start by sorting the array nums. Sorting helps us easily access and remove the smallest and largest elements in each iteration by simply accessing the elements at the beginning and the end of the list.
Iterating and Pairing: With the sorted array, we iterate for n/2 steps, where n is the total number of elements in nums. In each step, calculate the sum of the smallest element and the largest element that has not yet been used. This is achieved by selecting nums[i] and nums[-i - 1] for each iteration i ranging from 0 to n/2 - 1.
Storing and Finding Minimum Average: Instead of maintaining an averages array, simply keep track of the minimum of these computed sums. Dividing each sum by 2 on-the-go, update the minimum value found.
Return Result: At the end of the iteration, return the minimum average found. This is done by considering the smallest computed sum divided by 2.

The solution is effectively captured in this line of code from the implementation:

return min(nums[i] + nums[-i - 1] for i in range(n // 2)) / 2

This approach efficiently computes the desired minimum average by leveraging sorting alongside a linear scan, resulting in a time complexity dominated by the sorting operation, i.e., O(n log n).

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose nums = [8, 1, 7, 3, 6, 2].

Step 1: Sorting

First, we sort the array nums. The sorted array is [1, 2, 3, 6, 7, 8].

Step 2: Iterating and Pairing

Next, we iterate n/2 times (n is 6 here, so n/2 is 3). In each iteration, we pair the smallest unprocessed element with the largest unprocessed element:

Iteration 1: Pair 1 and 8. Their average is (1 + 8) / 2 = 4.5.
Iteration 2: Pair 2 and 7. Their average is (2 + 7) / 2 = 4.5.
Iteration 3: Pair 3 and 6. Their average is (3 + 6) / 2 = 4.5.

Step 3 & 4: Storing and Finding Minimum Average

We keep track of the minimum of these averages. In this example, all computed averages are 4.5, so the minimum average is 4.5.

Return Result

Finally, the smallest average from these pairings is 4.5, which is returned as the result.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumAverage(self, nums: List[int]) -> float:
5        # Sort the array to facilitate pairing elements.
6        nums.sort()
7      
8        # Calculate the length of the list.
9        n = len(nums)
10      
11        # Calculate the minimum sum of paired elements. 
12        # Pairs are formed by adding the smallest and largest available numbers, moving towards the middle.
13        # The result is the minimum sum divided by 2 to get the average value.
14        min_sum = min(nums[i] + nums[n - i - 1] for i in range(n // 2))
15      
16        return min_sum / 2
17

1import java.util.Arrays;
2
3class Solution {
4    public double minimumAverage(int[] nums) {
5        // Sort the array to facilitate the process of finding minimum pairs
6        Arrays.sort(nums);
7        int n = nums.length;
8      
9        // Start with a large initial value for the answer
10        int ans = 1 << 30;
11      
12        // Iterate through the first half of the sorted array
13        for (int i = 0; i < n / 2; ++i) {
14            // Compare and take the minimum of the current answer and the sum of pair
15            ans = Math.min(ans, nums[i] + nums[n - i - 1]);
16        }
17      
18        // Return the smallest found pair sum, divided by 2, as a double
19        return ans / 2.0;
20    }
21}
22

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5class Solution {
6public:
7    double minimumAverage(std::vector<int>& nums) {
8        // Sort the input vector in non-decreasing order
9        std::sort(nums.begin(), nums.end());
10
11        // Initialize 'minimumSum' with a very large value
12        int minimumSum = INT_MAX;
13        int n = nums.size(); // Get the size of the vector
14
15        // Iterate over the first half of the sorted vector
16        for (int i = 0; i < n; ++i) {
17            // Calculate the sum of the i-th element and its corresponding element from the end
18            minimumSum = std::min(minimumSum, nums[i] + nums[n - i - 1]);
19        }
20
21        // Return the minimum sum divided by 2 as a double to get the average
22        return minimumSum / 2.0;
23    }
24};
25

1// Function to calculate the minimum average sum of pairs in a sorted array
2function minimumAverage(nums: number[]): number {
3    // Sort the array in ascending order
4    nums.sort((a, b) => a - b);
5
6    const length = nums.length; // Get the total number of elements in the array
7    let minimumSum = Infinity;  // Initialize the minimum sum to a very large value
8
9    // Iterate through the first half of the array
10    for (let i = 0; i * 2 < length; ++i) {
11        // Calculate the sum of the ith element and its corresponding element from the end of the array
12        minimumSum = Math.min(minimumSum, nums[i] + nums[length - 1 - i]);
13    }
14
15    // Return the minimum sum divided by 2 to get the average
16    return minimumSum / 2;
17}
18

Time and Space Complexity

The time complexity of the code is O(n \log n), due to the sorting operation performed on the list nums. Sorting a list of n elements typically requires O(n \log n) time.

The space complexity of the code is O(\log n), primarily because some sorting algorithms, like Timsort (used by Python's built-in sort), require additional space for recursive calls, which typically amounts to O(\log n).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know