SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The problem requires us to repeatedly find pairs of smallest and largest elements from an array, compute their average, and then find the minimum of these averages. This suggests a strategy where we efficiently maintain and update the smallest and largest elements while iterating through the array.

Approach

1. Sort the Array: Start by sorting the given array nums of integers.

2. Iterate through Pairs: Iterate over the sorted array in pairs from both ends towards the center:

   • For each iteration, pick the smallest (minElement) and largest (maxElement) elements from the current ends of the array.
   • Compute their average: avg = (minElement + maxElement) / 2.
   • Add this average to the averages array.

3. Compute Minimum: After populating the averages array with all computed averages, find the minimum value in this array.

4. Return Minimum: Return the computed minimum value from the averages array as the result.

Complexity

• Time Complexity:

  • Sorting the array takes (O(nlogn)).
  • Iterating through the array and computing averages takes (O(n)).
  • Finding the minimum in the averages array takes (O(n/2)).
  • Overall, the time complexity is dominated by the sorting step, (O(nlogn)).

• Space Complexity:

  • Additional space used includes (O(n)) for storing the averages array.
  • Sorting might use (O(logn)) space for internal operations.
  • Therefore, the space complexity is (O(n)).

Code

C++

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

Python

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

Java

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

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumAverage = function (nums) {
  var res = 100;
  nums.sort((a, b) => a - b);
  for (var i = 0; i < nums.length >> 1; ++i) {
    res = Math.min(res, nums[i] + nums[nums.length - i - 1]);
  }
  return res / 2;
};

Go

func minimumAverage(nums []int) float64 {
    sort.Ints(nums)
    res := 100.0
    for i := 0; i < len(nums)/2; i++ {
        res = math.Min(res, float64(nums[i]+nums[len(nums)-i-1]))
    }
    return res / 2
}

C#

public class Solution {
    public double MinimumAverage(int[] nums) {
        double res = 100;
        Array.Sort(nums);
        for (int i = 0; i < nums.Length / 2; ++i) {
            res = Math.Min(res, nums[i] + nums[nums.Length - i - 1]);
        }
        return res / 2;
    }
}