2091. Removing Minimum and Maximum From Array

Problem Overview

You only need to remove the current minimum and maximum.

Intuition

You only need to remove the current minimum and maximum. Removals happen from either end, so the cheapest plan is one of three patterns: delete everything from the left through the farther of the two, delete everything from the right through the nearer of the two, or delete one from the left and one from the right. Scan once to find the two indices, then take the minimum of those three costs.

Algorithm

1Scan nums and record the index of the smallest value and the largest value.
2Let a = min(minIndex, maxIndex) and b = max(minIndex, maxIndex).
3Cost both from the front: b + 1.
4Cost both from the back: n - a.
5Cost one from each end: a + 1 + n - b.
6Return the minimum of the three.

Example Walkthrough

Input: nums = [2, 10, 7, 5, 4, 1, 8, 6]

1.Min 1 is at index 5. Max 10 is at index 1. So a = 1, b = 5, n = 8.
2.Front: 5+1 = 6. Back: 8-1 = 7. Split: 1+1 + 8-5 = 5.
3.Best is 5: drop the left end once (10) and the right end four times until 1 is gone.

Output: 5

Common Pitfalls

•If min and max share the same index (n = 1), all three formulas still work and return 1.
•You must cover both indices. Deleting only through a from the front leaves b in the array.
•The split formula is a+1 from the left plus n-b from the right, not a+b.
•A second scan is unnecessary. One pass to find the two indices is enough.

2091.cs

// Approach: Find the indices of min and max. Any optimal plan is one of three:
// delete from the front through the farther index, from the back through the
// nearer index, or one from each end. Take the minimum of those three costs.
// Complexity: O(n) time and O(1) extra space.

public class Solution
{
    public int MinimumDeletions(int[] nums)
    {
        int n = nums.Length;

        int mn = int.MaxValue;
        int mx = int.MinValue;
        int minIndex = -1;
        int maxIndex = -1;

        for (int i = 0; i < n; ++i)
        {
            if (nums[i] < mn)
            {
                mn = nums[i];
                minIndex = i;
            }
            if (nums[i] > mx)
            {
                mx = nums[i];
                maxIndex = i;
            }
        }

        int a = Math.Min(minIndex, maxIndex);
        int b = Math.Max(minIndex, maxIndex);

        // min(delete from front and back,
        //     delete from front,
        //     delete from back)
        return Math.Min(a + 1 + n - b, Math.Min(b + 1, n - a));
    }
}

Was this solution helpful?