Taro Logo

Minimum Average of Smallest and Largest Elements

Easy
Amazon logo
Amazon
1 view
Topics:
ArraysTwo PointersGreedy Algorithms

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:

Input: nums = [7,8,3,4,15,13,4,1]
Output: 5.5

Explanation:

stepnumsaverages
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:

stepnumsaverages
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:

stepnumsaverages
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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the range of values that the numbers in the array can have? Are negative numbers allowed?
  2. What should I return if the input array is empty or contains only one element?
  3. Are duplicate numbers allowed in the array, and if so, how should they be handled when calculating the average of the smallest and largest elements?
  4. Can you provide an example of an input array and the expected output to clarify the problem statement further?
  5. Is there any constraint on the size of the input array?

Brute Force Solution

Approach

The brute force approach is like trying every single possible combination to find the best one. In this problem, we want to find a small section of numbers where the average of the smallest and largest numbers within that section is the smallest across all possible sections.

Here's how the algorithm would work step-by-step:

  1. Consider every possible section of numbers, starting with a section of just one number.
  2. Then, look at every possible section of two numbers, then three, and so on, until you've looked at a section that includes all the numbers.
  3. For each section, find the smallest and largest numbers within that section.
  4. Calculate the average of the smallest and largest numbers for that particular section.
  5. Keep track of the smallest average you've found so far.
  6. If the average you just calculated is smaller than the smallest average you've found so far, update your record to remember this new smallest average.
  7. Once you've examined every possible section, the smallest average you've recorded is your answer.

Code Implementation

def minimum_average_of_smallest_and_largest_elements_brute_force(numbers):
    minimum_average = float('inf')

    # Iterate through all possible sub-arrays.
    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):

            sub_array = numbers[start_index:end_index + 1]

            # Find the smallest and largest numbers.
            smallest_number = min(sub_array)

            largest_number = max(sub_array)

            # Calculate the average.
            current_average = (smallest_number + largest_number) / 2

            # Update the minimum average if necessary.
            if current_average < minimum_average:

                # Keep track of the minimum average
                minimum_average = current_average

    return minimum_average

Big(O) Analysis

Time Complexity
O(n³)The algorithm iterates through all possible subarrays of the input array of size n. There are approximately n * (n+1) / 2 such subarrays. For each subarray, the algorithm finds the minimum and maximum element, which takes O(n) time in the worst case. Thus, the overall time complexity is proportional to (n * (n+1) / 2) * n, which simplifies to O(n³).
Space Complexity
O(1)The provided plain English explanation describes an iterative approach that examines all possible sub-arrays. For each sub-array, it calculates the minimum and maximum, then computes their average. The only extra space required is for storing a few variables: the current minimum, the current maximum, the current average of a sub-array, and the overall minimum average seen so far. These variables use a constant amount of memory, independent of the input array's size (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The core idea is to cleverly sort and pair numbers to minimize the average. We focus on matching the smallest numbers with the largest numbers to keep the averages low from the start.

Here's how the algorithm would work step-by-step:

  1. First, arrange the list of numbers in ascending order from smallest to largest.
  2. Then, pair the smallest number with the largest number, the second smallest with the second largest, and so on.
  3. For each pair, calculate their average by adding them together and dividing by two.
  4. Finally, find the smallest average among all the calculated averages. That is your answer.

Code Implementation

def find_minimum_average_of_smallest_and_largest_elements(number_list):
    number_list.sort()

    minimum_average = float('inf')

    # Pair smallest with largest to minimize averages
    for i in range(len(number_list) // 2):
        current_average = (number_list[i] + number_list[len(number_list) - 1 - i]) / 2
        # Compare against the lowest average found so far.
        minimum_average = min(minimum_average, current_average)

    if len(number_list) % 2 != 0:
        # If odd number of elements, account for middle element.
        middle_element = number_list[len(number_list) // 2]
        minimum_average = min(minimum_average, middle_element)

    return minimum_average

Big(O) Analysis

Time Complexity
O(n log n)The dominant operation in this algorithm is sorting the input array of size n. Common sorting algorithms like merge sort or quicksort have a time complexity of O(n log n). The pairing and averaging steps involve iterating through the sorted array once, which takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step. Therefore, the algorithm's time complexity is O(n log n).
Space Complexity
O(1)The provided solution primarily sorts the input array in place. Beyond the input, we only store a few variables: indices for pairing (e.g., first and last) and a variable to track the minimum average found so far. These variables require a constant amount of extra memory, independent of the input size N. Therefore, the space complexity is O(1).

Edge Cases

CaseHow to Handle
Empty input arrayReturn an empty list or null to indicate no minimum average can be computed.
Array with only one elementReturn an empty list or null, as a minimum average requires at least two numbers.
Array with all identical elementsThe algorithm should correctly compute the average of any pair of these identical numbers, selecting the minimum.
Array with only two elementsCalculate and return the average of these two elements as the only possible result.
Array containing very large numbers leading to potential integer overflowUse a data type capable of holding the sum of two large numbers (e.g., long, BigInteger), and divide using floating-point to avoid integer division issues.
Array with a large number of elements (scalability)Optimize the algorithm for time complexity (e.g., avoid nested loops if possible) and consider space complexity for auxiliary data structures.
Array containing negative numbersThe algorithm should correctly handle negative numbers when calculating the minimum average, including comparing positive and negative averages.
Array containing zeroZero should be handled correctly when calculating the averages, including comparing averages with zero or negative averages.