Minimum removals from array to make max min less than or equal to K

The problem, simply

You get a list of numbers and a number K. Remove as few numbers as you can so that, in what is left, the biggest minus the smallest is at most K.

Give back how many numbers you removed. Removing everything except one number always works, so the answer is at most n - 1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Sort first. If the group from position i to position j does not fit, one of its two ends must go: either the shortest or the tallest. Try both.

1. remove(i, j) is the fewest removals that make a[i..j] fit.
2. If a[j] - a[i] <= K, it already fits: 0.
3. Otherwise it is 1 + min(remove(i + 1, j), remove(i, j - 1)).

Removing someone from the middle never helps, because the middle does not change the biggest or the smallest.

import java.util.Arrays;

class Solution {
    public int minRemovals(int[] arr, int k) {
        int[] a = arr.clone();
        Arrays.sort(a);
        return remove(a, 0, a.length - 1, k);
    }

    private int remove(int[] a, int i, int j, int k) {
        if (i >= j || a[j] - a[i] <= k) return 0;           // this group already fits
        int dropShort = remove(a, i + 1, j, k);             // send the shortest home
        int dropTall = remove(a, i, j - 1, k);              // send the tallest home
        return 1 + Math.min(dropShort, dropTall);
    }
}

How long it takes: two branches per call, up to n deep, O(2^n). Extra room: the waiting calls, O(n). The same group (i, j) is solved many times.

Way 2: the clever way

Since the kept group is a stretch of the sorted line, find the longest stretch whose ends differ by at most K. Then the answer is n minus its length.

1. Sort.
2. Move right from left to right. After adding a[right], move left forward while a[right] - a[left] > K.
3. The window left..right now fits. Remember the biggest window size.
4. Return n - biggest.

left never moves back, so each number enters and leaves the window at most once.

import java.util.Arrays;

class Solution {
    public int minRemovals(int[] arr, int k) {
        int n = arr.length;
        int[] a = arr.clone();
        Arrays.sort(a);                                 // fitting groups become stretches
        int left = 0, keep = 0;
        for (int right = 0; right < n; right++) {
            while (a[right] - a[left] > k) left++;      // too tall: shrink from the left
            keep = Math.max(keep, right - left + 1);
        }
        return n - keep;
    }
}

How long it takes: sorting is O(n log n), and the window walk is O(n). Extra room: two pointers, O(1), apart from the sorted copy.

Another way: the DP table

Way 1 only ever asks about groups (i, j) of the sorted list, so there are n * n / 2 different questions. Save each answer in a table and you get the classic DP: O(n^2) time and room. Short groups are filled first, because a group's answer needs the groups one shorter.

import java.util.Arrays;

class Solution {
    public int minRemovals(int[] arr, int k) {
        int n = arr.length;
        if (n == 0) return 0;
        int[] a = arr.clone();
        Arrays.sort(a);
        int[][] dp = new int[n][n];                     // dp[i][j]: removals so a[i..j] fits
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (a[j] - a[i] <= k) dp[i][j] = 0;
                else dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}

The window in Way 2 is better in every way, but interviewers sometimes ask for this table to see if you can turn a recursion into DP.

Watch out for

• The rule is "at most K": use > k to shrink the window, not >= k.
• Return the number removed (n - keep), not the number kept.
• An empty list needs 0 removals. The window code handles it, the table code needs the n == 0 check.

What interviewers ask next

• What if you may only remove from the two ends of the original, unsorted list? Then you cannot sort. The kept part is a stretch of the original list. Use the DP on the original order, or a sliding window with two deques that track the min and the max, O(n).
• Count how many groups (stretches) fit. In the window loop, add right - left + 1 each time.
• Each kid has a value and you want to keep the most total value? Same sorted window, but track the window's sum instead of its size.
• Can you avoid sorting? If the values are small integers, count them in buckets and slide over the buckets.

Remember this

Grown-up words: the photo line is the sorted array, the frame is a sliding window with two pointers, the table version is interval DP over (i, j), and the repeated groups in the recursion are overlapping subproblems.