Example: Minimum Inefficiency Problem - rFronteddu/general_wiki GitHub Wiki

Given an array of integers, you want to select k elements such that the inefficiency is minimized, where inefficiency is defined as:

inefficiency = max (selected elements) − min (selected elements)

Approach

1. Sort the Array: First, sort the array of integers. This allows us to evaluate potential groups of k elements easily.
2. Sliding Window Approach: Use a sliding window of size k to traverse through the sorted array. For each window (subarray of size k), compute the inefficiency.
3. Track Minimum Inefficiency: Maintain a variable to keep track of the minimum inefficiency encountered while sliding through the array.

import java.util.Arrays;

public class MinimumInefficiency {
    public static int getMinimumInefficiency(int[] nums, int k) {
        // Step 1: Sort the array
        Arrays.sort(nums);

        int minInefficiency = Integer.MAX_VALUE;

        // Step 2: Use a sliding window to find the minimum inefficiency
        for (int i = 0; i <= nums.length - k; i++) {
            // Inefficiency of the current window of size k
            int inefficiency = nums[i + k - 1] - nums[i];
            minInefficiency = Math.min(minInefficiency, inefficiency);
        }

        return minInefficiency;
    }
}