2091. Removing Minimum and Maximum From Array

Intuition

Deletions only ever come off the two ends, so whatever we do, the elements removed form a prefix and a suffix. The values in between are irrelevant, all that matters is where the minimum and maximum sit.

Let lo and hi be the two positions, ordered so lo <= hi. To remove both, every strategy falls into one of three shapes:

• Take both from the front, the prefix must reach the further one: hi + 1 deletions.
• Take both from the back, the suffix must reach the nearer one: n - lo deletions.
• Take one from each end, a prefix covering lo (lo + 1) plus a suffix covering hi (n - hi).

Nothing else is possible, so the answer is just the smallest of the three.

Approach

1. Scan once to find the index of the minimum and the index of the maximum.
2. Set lo = min(i, j), hi = max(i, j).
3. Return min(hi + 1, n - lo, (lo + 1) + (n - hi)).

Complexity

• Time: O(n), a single pass to locate both indices
• Space: O(1)

Edge Cases

• Single element (Example 3) → it is both min and max; lo == hi == 0 and the front/back options both give 1, beating the split option's 2
• Min and max adjacent → the front or back option usually wins (Example 2)
• Min and max at opposite ends → the split option costs exactly 2
• Values are distinct, so the min and max positions are unambiguous
• The split option can be worse than either single-sided option, so all three must be compared

from typing import List


class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        """
        2091. Removing Minimum and Maximum From Array
        Time: O(n)
        Space: O(1)
        """
        n = len(nums)
        min_idx = min(range(n), key=lambda i: nums[i])
        max_idx = max(range(n), key=lambda i: nums[i])
        lo, hi = min(min_idx, max_idx), max(min_idx, max_idx)

        both_front = hi + 1
        both_back = n - lo
        split = (lo + 1) + (n - hi)
        return min(both_front, both_back, split)

/**
 * 2091. Removing Minimum and Maximum From Array
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int minimumDeletions(int[] nums) {
        int n = nums.length;
        int minIdx = 0, maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            }
        }

        int lo = Math.min(minIdx, maxIdx);
        int hi = Math.max(minIdx, maxIdx);

        int bothFront = hi + 1;
        int bothBack = n - lo;
        int split = (lo + 1) + (n - hi);
        return Math.min(bothFront, Math.min(bothBack, split));
    }
}