Jobs

Interviews

Discussions

Mean of Array After Removing Some Elements

Easy

Asked by:

24 views

Topics:

Arrays

Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements.

Answers within 10^-5 of the actual answer will be considered accepted.

Example 1:

Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
Output: 2.00000
Explanation: After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.

Example 2:

Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
Output: 4.00000

Example 3:

Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
Output: 4.77778

Constraints:

20 <= arr.length <= 1000
arr.length is a multiple of 20.
0 <= arr[i] <= 10⁵

Try coding it in LeetCode

Mean of Array After Removing Some Elements

Easy

Asked by:

24 views

Topics:

Arrays

Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements.

Answers within 10^-5 of the actual answer will be considered accepted.

Example 1:

Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
Output: 2.00000
Explanation: After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.

Example 2:

Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
Output: 4.00000

Example 3:

Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
Output: 4.77778

Constraints:

20 <= arr.length <= 1000
arr.length is a multiple of 20.
0 <= arr[i] <= 10⁵

Try coding it in LeetCode

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:

What are the constraints on the number of elements to remove; is it a fixed number or a percentage?
Can the input array contain negative numbers, zeros, or floating-point numbers?
What should I return if the input array is empty or if after removing the specified number of elements, the remaining array is empty?
If there are multiple ways to remove the elements such that the resulting mean is the same, is any solution acceptable?
What is the data type of the returned mean; should I round it, truncate it, or return it with full precision?

Brute Force Solution

Approach

The brute force way to find the mean after removing some elements means trying every single possible combination of elements to remove. Then for each removal, we calculate the mean and track the best one. It's like testing out every single possibility and picking the winner.

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

First, consider the scenario where you remove no elements at all.
Calculate the mean of all the numbers in the array in this case.
Now, consider removing only one element and try removing each element one at a time and calculate the mean of the remaining numbers.
Next, consider removing two elements. Again, try every possible pair of elements you could remove, calculating the mean of the remaining numbers after each removal.
Continue this process, removing three elements, four elements, and so on, until you've considered removing the maximum allowable number of elements.
Keep track of the mean that results from each removal scenario.
Finally, compare all the calculated means, and select the largest one as the final result.

Code Implementation

def mean_after_removing_elements_brute_force(numbers, k_elements_to_remove):
    best_mean = float('-inf')

    number_of_elements = len(numbers)

    # Iterate through all possible combinations of elements to remove.
    for i in range(1 << number_of_elements):
        elements_removed_count = 0
        current_subset = []

        # Determine which elements are to be removed based on the bitmask.
        for j in range(number_of_elements):
            if (i >> j) & 1:
                elements_removed_count += 1
            else:
                current_subset.append(numbers[j])

        # Only consider combinations where the correct number of elements are removed.
        if elements_removed_count == k_elements_to_remove:

            #Calculate the mean of the current subset.
            if len(current_subset) > 0:
                current_sum = sum(current_subset)
                current_mean = current_sum / len(current_subset)

                #Keep track of the best mean found so far.
                best_mean = max(best_mean, current_mean)

    if best_mean == float('-inf'):
        return 0.0
    else:
        return best_mean

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach involves considering all possible subsets of elements to remove. For each element in the array of size n, we have two choices: either remove it or keep it. This results in 2^n possible subsets. For each subset, we calculate the mean of the remaining elements, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2^n). However, since the problem implies that we are only removing a subset, and calculating the mean each time and choosing the best. This suggests we remove 1, 2, 3... up to k elements (where k is probably <= n). The number of combinations we need to calculate is given by n choose 1 + n choose 2 + ... + n choose k. In the worst case k=n, then we have n choose 0 + n choose 1 + ... + n choose n which is equal to 2^n. Computing the mean will be O(n) so the runtime is O(n * 2^n). The question suggests to remove a fixed number of elements at a time and calculate the mean of the remainder. Therefore we should consider the approach is about examining all subsets but the explanation doesn't include memoization or pruning, and does not leverage the value of the elements in the array. Since it is implied that k elements will be removed for all k from 0 to n this would still be O(2^n).

Space Complexity

O(1) – The described brute force approach calculates the mean for each possible subset of the array after removing elements. The only extra memory used is to store the current maximum mean found and the sum of the current subset to calculate the mean. These variables take up constant space, regardless of the input array's size N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The task is to find the average of a collection of numbers after removing the smallest and largest few. A clever approach involves figuring out what the numbers that are not going to be part of the final calculation are, and calculating the sum of the others, then doing the division.

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

First, organize the numbers from smallest to largest.
Figure out exactly how many of the smallest numbers need to be removed from consideration.
Figure out exactly how many of the largest numbers need to be removed from consideration.
Calculate the sum of all the numbers excluding the ones identified for removal in the previous two steps.
Count how many numbers were actually included in the sum.
Divide the sum by the count to get the final average, which is your answer.

Code Implementation

def calculate_trimmed_mean(array_of_numbers, trim_percentage):
    array_length = len(array_of_numbers)
    trim_amount = int(array_length * trim_percentage / 100)

    array_of_numbers.sort()

    # Dropping elements from the beginning and end of the array.
    trimmed_array = array_of_numbers[trim_amount:array_length - trim_amount]

    trimmed_array_length = len(trimmed_array)

    # Avoid division by zero if the trimmed array is empty
    if trimmed_array_length == 0:
        return 0.0

    total_sum = sum(trimmed_array)

    # Dividing the sum by the number of included elements
    average_value = total_sum / trimmed_array_length

    return average_value

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this approach is sorting the input array of size n in step 1. Common sorting algorithms like merge sort or quicksort have a time complexity of O(n log n). Steps 2 and 3 involve simple arithmetic calculations and take constant time, O(1). Step 4 iterates through a portion of the sorted array to calculate the sum, which takes O(n) time. Step 5 and 6 are also constant time operations, O(1). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in place. Beyond the input array, we use a few integer variables to store the sum and count of included elements, along with the number of elements to remove from the beginning and end of the array. These variables consume constant space, irrespective of the input size N. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an exception, depending on the requirements specified in the problem statement, since no mean can be calculated.
Input array with size equal to k (elements to remove) or less	Return 0, as after removing the elements, nothing remains to calculate the mean from.
Input array with all elements having the same value	The solution should still calculate the mean of the remaining elements correctly after removing k smallest and k largest.
Input array containing negative numbers	The sorting algorithm should correctly handle negative numbers, ensuring the smallest and largest are identified accurately.
Input array containing zero values	The sorting algorithm should correctly place zero values in the sorted array so the trimming handles it properly.
Large input array that may cause memory issues during sorting.	Consider using an in-place sorting algorithm or a more memory-efficient data structure if memory becomes a constraint.
Input array with extreme values (very large or very small) that could cause overflow issues.	Use appropriate data types (e.g., long) or consider scaling the values down if possible to prevent integer overflow during the mean calculation.
k is larger than half the array size	Adjust k to be half of array size to prevent array index out of bounds exceptions.

Null or empty input array

How to Handle:

Return 0 or throw an exception, depending on the requirements specified in the problem statement, since no mean can be calculated.

Input array with size equal to k (elements to remove) or less

How to Handle:

Return 0, as after removing the elements, nothing remains to calculate the mean from.

Input array with all elements having the same value

How to Handle:

The solution should still calculate the mean of the remaining elements correctly after removing k smallest and k largest.

Input array containing negative numbers

How to Handle:

The sorting algorithm should correctly handle negative numbers, ensuring the smallest and largest are identified accurately.

Input array containing zero values

How to Handle:

The sorting algorithm should correctly place zero values in the sorted array so the trimming handles it properly.

Large input array that may cause memory issues during sorting.

How to Handle:

Consider using an in-place sorting algorithm or a more memory-efficient data structure if memory becomes a constraint.

Input array with extreme values (very large or very small) that could cause overflow issues.

How to Handle:

Use appropriate data types (e.g., long) or consider scaling the values down if possible to prevent integer overflow during the mean calculation.

k is larger than half the array size

How to Handle:

Adjust k to be half of array size to prevent array index out of bounds exceptions.

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:

What are the constraints on the number of elements to remove; is it a fixed number or a percentage?
Can the input array contain negative numbers, zeros, or floating-point numbers?
What should I return if the input array is empty or if after removing the specified number of elements, the remaining array is empty?
If there are multiple ways to remove the elements such that the resulting mean is the same, is any solution acceptable?
What is the data type of the returned mean; should I round it, truncate it, or return it with full precision?

Brute Force Solution

Approach

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

First, consider the scenario where you remove no elements at all.
Calculate the mean of all the numbers in the array in this case.
Now, consider removing only one element and try removing each element one at a time and calculate the mean of the remaining numbers.
Next, consider removing two elements. Again, try every possible pair of elements you could remove, calculating the mean of the remaining numbers after each removal.
Continue this process, removing three elements, four elements, and so on, until you've considered removing the maximum allowable number of elements.
Keep track of the mean that results from each removal scenario.
Finally, compare all the calculated means, and select the largest one as the final result.

Code Implementation

def mean_after_removing_elements_brute_force(numbers, k_elements_to_remove):
    best_mean = float('-inf')

    number_of_elements = len(numbers)

    # Iterate through all possible combinations of elements to remove.
    for i in range(1 << number_of_elements):
        elements_removed_count = 0
        current_subset = []

        # Determine which elements are to be removed based on the bitmask.
        for j in range(number_of_elements):
            if (i >> j) & 1:
                elements_removed_count += 1
            else:
                current_subset.append(numbers[j])

        # Only consider combinations where the correct number of elements are removed.
        if elements_removed_count == k_elements_to_remove:

            #Calculate the mean of the current subset.
            if len(current_subset) > 0:
                current_sum = sum(current_subset)
                current_mean = current_sum / len(current_subset)

                #Keep track of the best mean found so far.
                best_mean = max(best_mean, current_mean)

    if best_mean == float('-inf'):
        return 0.0
    else:
        return best_mean

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, organize the numbers from smallest to largest.
Figure out exactly how many of the smallest numbers need to be removed from consideration.
Figure out exactly how many of the largest numbers need to be removed from consideration.
Calculate the sum of all the numbers excluding the ones identified for removal in the previous two steps.
Count how many numbers were actually included in the sum.
Divide the sum by the count to get the final average, which is your answer.

Code Implementation

def calculate_trimmed_mean(array_of_numbers, trim_percentage):
    array_length = len(array_of_numbers)
    trim_amount = int(array_length * trim_percentage / 100)

    array_of_numbers.sort()

    # Dropping elements from the beginning and end of the array.
    trimmed_array = array_of_numbers[trim_amount:array_length - trim_amount]

    trimmed_array_length = len(trimmed_array)

    # Avoid division by zero if the trimmed array is empty
    if trimmed_array_length == 0:
        return 0.0

    total_sum = sum(trimmed_array)

    # Dividing the sum by the number of included elements
    average_value = total_sum / trimmed_array_length

    return average_value

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an exception, depending on the requirements specified in the problem statement, since no mean can be calculated.
Input array with size equal to k (elements to remove) or less	Return 0, as after removing the elements, nothing remains to calculate the mean from.
Input array with all elements having the same value	The solution should still calculate the mean of the remaining elements correctly after removing k smallest and k largest.
Input array containing negative numbers	The sorting algorithm should correctly handle negative numbers, ensuring the smallest and largest are identified accurately.
Input array containing zero values	The sorting algorithm should correctly place zero values in the sorted array so the trimming handles it properly.
Large input array that may cause memory issues during sorting.	Consider using an in-place sorting algorithm or a more memory-efficient data structure if memory becomes a constraint.
Input array with extreme values (very large or very small) that could cause overflow issues.	Use appropriate data types (e.g., long) or consider scaling the values down if possible to prevent integer overflow during the mean calculation.
k is larger than half the array size	Adjust k to be half of array size to prevent array index out of bounds exceptions.

Null or empty input array

How to Handle:

Return 0 or throw an exception, depending on the requirements specified in the problem statement, since no mean can be calculated.

Input array with size equal to k (elements to remove) or less

How to Handle:

Return 0, as after removing the elements, nothing remains to calculate the mean from.

Input array with all elements having the same value

How to Handle:

The solution should still calculate the mean of the remaining elements correctly after removing k smallest and k largest.

Input array containing negative numbers

How to Handle:

The sorting algorithm should correctly handle negative numbers, ensuring the smallest and largest are identified accurately.

Input array containing zero values

How to Handle:

The sorting algorithm should correctly place zero values in the sorted array so the trimming handles it properly.

Large input array that may cause memory issues during sorting.

How to Handle:

Consider using an in-place sorting algorithm or a more memory-efficient data structure if memory becomes a constraint.

Input array with extreme values (very large or very small) that could cause overflow issues.

How to Handle:

Use appropriate data types (e.g., long) or consider scaling the values down if possible to prevent integer overflow during the mean calculation.

k is larger than half the array size

How to Handle:

Adjust k to be half of array size to prevent array index out of bounds exceptions.