{x}
blog image

Removing Minimum and Maximum From Array

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.

 

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.

 

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • The integers in nums are distinct.

Solution Explanation

The problem asks for the minimum number of deletions needed to remove both the minimum and maximum elements from an array. A deletion can be from either the front or back of the array.

The optimal solution involves considering three possibilities:

  1. Removing elements from the front: Delete all elements up to and including the maximum element. This requires mx + 1 deletions, where mx is the index of the maximum element.

  2. Removing elements from the back: Delete all elements from the minimum element to the end of the array. This requires n - mi deletions, where mi is the index of the minimum element and n is the length of the array.

  3. Removing elements from both ends: Delete elements from the front up to the minimum element and elements from the back up to the maximum element. This requires mi + 1 + n - mx deletions (assuming mi < mx). If mx < mi, we switch mi and mx before calculating this value.

The algorithm finds the indices of the minimum and maximum elements, and then calculates the minimum number of deletions based on these three possibilities.

Time Complexity Analysis

  • Finding the indices of minimum and maximum elements takes O(n) time, where n is the length of the array.
  • Calculating the minimum number of deletions among the three possibilities takes O(1) time.

Therefore, the overall time complexity of the solution is O(n).

Space Complexity Analysis

The solution uses a constant amount of extra space to store the indices of the minimum and maximum elements. Therefore, the space complexity is O(1).

Code Explanation (Python)

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        mi = mx = 0  # Initialize indices of minimum and maximum elements
        for i, num in enumerate(nums):
            if num < nums[mi]:
                mi = i  # Update minimum index if a smaller element is found
            if num > nums[mx]:
                mx = i  # Update maximum index if a larger element is found
 
        # Ensure mi < mx for consistent calculation in the next step
        if mi > mx:
            mi, mx = mx, mi
 
        # Calculate minimum deletions among three possibilities
        return min(mx + 1, len(nums) - mi, mi + 1 + len(nums) - mx)

The Python code directly implements the logic described above. It iterates through the array once to find the indices of the minimum and maximum elements. Then, it calculates the minimum deletions using the min() function, considering the three possibilities.

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithm and has the same time and space complexity. They differ only in syntax and specific language features.