algoadvance

Leetcode 1619. Mean of Array After Removing Some Elements

Problem Statement

You are given an integer array arr. Using a sliding window, find the mean of the array after dropping the smallest 5% and the largest 5% of the elements.

Constraints:

  1. 20 <= arr.length <= 1000
  2. arr.length is a multiple of 20.
  3. -10^5 <= arr[i] <= 10^5

Clarifying Questions

  1. Input Size: The input array has a length that is a multiple of 20 and ranges from 20 to 1000 elements.
  2. Sorting: To find the smallest and largest elements efficiently, sorting seems like a reasonable approach.
  3. 5% Calculation: We’ll need to drop exactly 5% of the smallest and largest elements, respectively.

Strategy

  1. Sort the Array: First, sort the array.
  2. Calculate Indices: Calculate the number of elements to remove, which is 5% of the array’s length.
  3. Compute the Mean: Calculate the mean of the remaining elements after removing the smallest and largest 5% of elements.

Code

import java.util.Arrays;

public class MeanAfterRemoval {
    public static double trimMean(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        int removeCount = n / 20;
        
        int sum = 0;
        for (int i = removeCount; i < n - removeCount; i++) {
            sum += arr[i];
        }
        
        double mean = (double) sum / (n - 2 * removeCount);
        return mean;
    }

    public static void main(String[] args) {
        int[] arr = {6,2,7,5,1,2,0,9,8,12,2,3,4,5,2,7,8,3,11,6,
                     4,6,9,5,4,5,6,5,8,10,2,3,5,6,8,9,10,11,12,14};
        System.out.println("Trimmed Mean: " + trimMean(arr));
    }
}

Time Complexity

Explanation

  1. Sorting the Array: We sort the array to easily remove the smallest and largest elements.
  2. Removing 5% Elements: By calculating the number of elements to remove (5% of array length), we straightforwardly drop those elements from both ends of the sorted array.
  3. Calculating the Mean: Summing the remaining elements and dividing by the new length (original length minus 10%) gives the correct mean.

This approach ensures that we account for removing extreme values to find a reliable mean of the trimmed array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI