Problem

You are given a 0-indexed array of distinct integers nums.

There is an element in nums that has the lowest value and an element that has the highest value. We call them the minimum and maximum respectively. Your goal is to remove both these elements from the array.

A deletion is defined as either removing an element from the front of the array or removing an element from the back of the array.

Return the minimum number of deletions it would take to remove both the minimum and maximum element from the array.

Examples

Example 1:

Input: nums = [2,**10**,7,5,4,**1**,8,6]
Output: 5
Explanation: 
The minimum element in the array is nums[5], which is 1.
The maximum element in the array is nums[1], which is 10.
We can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.
This results in 2 + 3 = 5 deletions, which is the minimum number possible.

Example 2:

Input:
nums = [0,**-4**,**19**,1,8,-2,-3,5]
Output:
 3
Explanation: 
The minimum element in the array is nums[1], which is -4.
The maximum element in the array is nums[2], which is 19.
We can remove both the minimum and maximum by removing 3 elements from the front.
This results in only 3 deletions, which is the minimum number possible.

Example 3:

Input:
nums = [**101**]
Output:
 1
Explanation:  
There is only one element in the array, which makes it both the minimum and maximum element.
We can remove it with 1 deletion.

Solution

Method 1 - Find indices of max and min and handle cases

Here is the approach:

  1. Determine the indices of the minimum and maximum values.
  2. Calculate the number of deletions needed for the following cases:
    • Remove both elements from the front.
    • Remove both elements from the back.
    • Remove one element from the front and the other from the back.
  3. Return the minimum deletions required from the above cases.

Code

Java
public class Solution {
    public int minDeletionsToRemoveMinMax(int[] nums) {
        int n = nums.length;
        int minIndex = 0, maxIndex = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        if (minIndex > maxIndex) {
            int temp = minIndex;
            minIndex = maxIndex;
            maxIndex = temp;
        }

        int deleteFromFront = maxIndex + 1;
        int deleteFromBack = n - minIndex;
        int deleteFromBoth = minIndex + 1 + n - maxIndex;

        return Math.min(Math.min(deleteFromFront, deleteFromBack), deleteFromBoth);
    }
}
Python
def minDeletionsToRemoveMinMax(nums):
    n = len(nums)
    min_index = nums.index(min(nums))
    max_index = nums.index(max(nums))

    if min_index > max_index:
        min_index, max_index = max_index, min_index

    delete_from_front = max_index + 1
    delete_from_back = n - min_index
    delete_from_both = min_index + 1 + n - max_index

    return min(delete_from_front, delete_from_back, delete_from_both)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, since we are iterating through the array to find the minimum and maximum indices.
  • 🧺 Space complexity: O(1), as we only use a constant amount of extra space.