373. Removing Minimum and Maximum From Array

Only the positions of the min and max matter. Deletions always peel from the two ends, so once we know how far each extreme sits from the front and the back, there are just three ways to remove both — take the cheapest.

Key insight

Deletions can only happen at the front or the back of the array. So the actual values of the elements are irrelevant except for one thing: where the minimum and the maximum sit. Let i be the index of the minimum and j the index of the maximum. Everything reduces to reaching both i and j by peeling from the two ends as cheaply as possible.

Let lo = min(i, j) and hi = max(i, j) — the leftmost and rightmost of the two extreme positions in a 0-indexed array of length n.

The three (and only three) strategies

1. Remove both from the front. To delete the element at index hi, we must first delete everything before it, so this costs hi + 1 deletions.
2. Remove both from the back. To delete the element at index lo, we must delete everything after it too, costing n - lo deletions.
3. Remove one from each side. Peel the closer-to-front extreme from the front (lo + 1 deletions) and the closer-to-back extreme from the back (n - hi deletions), for a total of (lo + 1) + (n - hi).

The answer is the minimum of these three.

Worked example

nums = [2,10,7,5,4,1,8,6], n = 8.

• The minimum is 1 at index 5, the maximum is 10 at index 1.
• lo = min(1, 5) = 1, hi = max(1, 5) = 5.
• Front only: hi + 1 = 6.
• Back only: n - lo = 8 - 1 = 7.
• Split: (lo + 1) + (n - hi) = 2 + 3 = 5.
• Minimum is 5 — remove 2 from the front (drops index 1, the max) and 3 from the back (drops index 5, the min).

So the answer is 5, matching the expected output.

Edge case

When n == 1 the single element is both the min and the max, i == j == 0, and all three formulas evaluate to 1 — one deletion removes it.

Complexity

• Time: O(n) — a single scan to locate the two extreme indices.
• Space: O(1) — only a handful of indices are tracked.

class Solution {
    public int minimumDeletions(int[] nums) {
        int n = nums.length;
        int imin = 0, imax = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[imin]) imin = i;
            if (nums[i] > nums[imax]) imax = i;
        }
        int lo = Math.min(imin, imax);
        int hi = Math.max(imin, imax);
        int front = hi + 1;
        int back = n - lo;
        int split = (lo + 1) + (n - hi);
        return Math.min(front, Math.min(back, split));
    }
}