Minimum removals from array to make max min less than or equal to K
Problem Statement
Given an array of integers and a value K, find the minimum number of elements to remove from the array so that the difference between the maximum and minimum elements of the remaining array is at most K.
Example:
- Input:
arr = [1, 3, 4, 9, 10, 11, 12, 17, 20], K = 4 - Output:
5(Keep [9, 10, 11, 12], remove 5 elements)
Noob-Friendly Explanation
Imagine you have a group of kids of different heights. You want to pick a group where the tallest and shortest kids differ by at most K inches. You want to pick the BIGGEST possible group (meaning you remove the fewest kids). How many kids do you need to send home to make the remaining group have heights within K of each other?
Approach 1: Brute Force
Intuition
Try all possible subsets of the array. For each subset, check if the difference between max and min is at most K. Track the largest valid subset — the answer is n - largest_subset_size.
Algorithm
- Generate all subsets of the array.
- For each subset, check if
max - min <= K. - Track the maximum valid subset size.
- Answer =
n - max_valid_size.
class Solution {
static int maxSubsetSize;
public static int minRemovalsBrute(int[] arr, int K) {
maxSubsetSize = 0;
generateSubsets(arr, 0, new java.util.ArrayList<>(), K);
return arr.length - maxSubsetSize;
}
private static void generateSubsets(int[] arr, int index,
java.util.ArrayList<Integer> current, int K) {
if (index == arr.length) {
if (!current.isEmpty()) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int val : current) {
min = Math.min(min, val);
max = Math.max(max, val);
}
if (max - min <= K) {
maxSubsetSize = Math.max(maxSubsetSize, current.size());
}
}
return;
}
// Include
current.add(arr[index]);
generateSubsets(arr, index + 1, current, K);
current.remove(current.size() - 1);
// Exclude
generateSubsets(arr, index + 1, current, K);
}
public static void main(String[] args) {
int[] arr = {1, 3, 4, 9, 10, 11, 12, 17, 20};
int K = 4;
System.out.println(minRemovalsBrute(arr, K)); // Output: 5
}
}Complexity Analysis
- Time Complexity: O(2^n) - generating all subsets
- Space Complexity: O(n) - recursion stack and current subset
Approach 2: Optimal
Intuition
Sort the array. After sorting, the valid elements must be a contiguous subarray (since we want max - min ≤ K). Use two pointers or binary search: for each element as the minimum, find the farthest element that is still within K.
Algorithm
- Sort the array.
- For each index
i, use binary search to find the rightmost indexjwherearr[j] - arr[i] <= K. - The window size
j - i + 1is the maximum elements we can keep witharr[i]as minimum. - Track the maximum window size. Answer =
n - max_window_size.
class Solution {
public static int minRemovals(int[] arr, int K) {
int n = arr.length;
java.util.Arrays.sort(arr);
int maxKeep = 0;
int left = 0;
for (int right = 0; right < n; right++) {
// Shrink window if difference exceeds K
while (arr[right] - arr[left] > K) {
left++;
}
maxKeep = Math.max(maxKeep, right - left + 1);
}
return n - maxKeep;
}
public static void main(String[] args) {
int[] arr = {1, 3, 4, 9, 10, 11, 12, 17, 20};
int K = 4;
System.out.println(minRemovals(arr, K)); // Output: 5
}
}Complexity Analysis
- Time Complexity: O(n log n) - dominated by sorting; the two-pointer pass is O(n)
- Space Complexity: O(1) - only a few variables (ignoring sort space)