Minimize Max Min Diff with Subarray Removal

Problem Overview

You delete one contiguous block of k cells and want the smallest gap between the largest and smallest value that remains.

Intuition

You delete one contiguous block of k cells and want the smallest gap between the largest and smallest value that remains. The surviving cells are always a prefix plus a suffix, and either side can be empty. Suffix minimums and maximums are built once by walking backward, and only suffixes that start at index k or later can remain. The prefix side grows as the deleted block slides right: it gains exactly the cell that just fell out of the block. Two running numbers track that prefix, so each candidate gap is a constant time combination of the two sides. When k is at least the array length, nothing remains and the gap is 0.

Algorithm

1Return 0 when k is at least n.
2Store the minimum and maximum of every suffix that starts at index k or later. There are n minus k such suffixes.
3Start the answer with the range of the suffix that begins at k, which is what remains after deleting the opening block.
4Slide the start of the block from 1 through n minus k minus 1. Combine the current prefix bounds with the suffix that begins just after the block, then fold the cell at the block start into the prefix.
5The prefix now covers everything except the final block. Take that range as well and return the smallest gap.

Example Walkthrough

Input: arr = [2, 3, 1, 4, 6, 7], k = 3

1. Deleting [2, 3, 1] leaves [4, 6, 7], and 7 minus 4 is 3.
2. Deleting [3, 1, 4] leaves [2, 6, 7], and 7 minus 2 is 5.
3. Deleting [1, 4, 6] leaves [2, 3, 7], and 7 minus 2 is 5.
4. Deleting [4, 6, 7] leaves [2, 3, 1], and 3 minus 1 is 2.

Output: 2

Common Pitfalls

• An empty side contributes no bound. The range comes only from the side that still has cells.
• Score the current window before growing the prefix. Updating the prefix first would count a cell that is still inside the deleted block.
• Suffix entries before index k still contain cells from the deleted block, so they are not stored.
• When k is 0 the block is empty, every cell remains, and the answer is the range of the whole array.

Minimize Max Min Diff with Subarray Removal.java

Java

// Approach: Removing one block of k cells leaves a prefix and a suffix. The
// minimum and maximum of every suffix that can remain are stored once. As
// the block slides right, the prefix bounds grow by the cell that just left
// the block, so each remaining range is scored in constant time. A removal
// that leaves no cell has difference 0.
// Complexity: O(n) time, O(n - k) extra space.
class Solution {
    public int minDiff(int k, int[] arr) {
        int n = arr.length;
        if (k >= n)
            return 0;

        int len = n - k;
        int[] suffixMin = new int[len];
        int[] suffixMax = new int[len];
        suffixMin[len - 1] = suffixMax[len - 1] = arr[n - 1];
        for (int i = len - 2; i >= 0; i--) {
            int value = arr[k + i];
            suffixMin[i] = Math.min(suffixMin[i + 1], value);
            suffixMax[i] = Math.max(suffixMax[i + 1], value);
        }

        int ans = suffixMax[0] - suffixMin[0];
        int prefixMin = arr[0];
        int prefixMax = arr[0];
        for (int i = 1; i < len; i++) {
            int min = Math.min(prefixMin, suffixMin[i]);
            int max = Math.max(prefixMax, suffixMax[i]);
            ans = Math.min(ans, max - min);
            prefixMin = Math.min(prefixMin, arr[i]);
            prefixMax = Math.max(prefixMax, arr[i]);
        }
        return Math.min(ans, prefixMax - prefixMin);
    }
}

Was this solution helpful?