#2091

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Removing Minimum and Maximum From Array

The problem asks to remove the minimum and maximum elements from an array with the fewest deletions.

Problem Statement

Given an array of distinct integers nums, find the minimum and maximum values in the array. You must remove both of these elements from the array using the fewest number of deletions.

A deletion can either be from the front or the back of the array. Your task is to return the minimum number of deletions required to remove both the minimum and maximum elements.

Examples

Example 1

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

Output: 5

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

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

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 Approach

Greedy Approach

The problem can be solved using a greedy strategy where you calculate the number of deletions required for each possible approach—deleting from the front, deleting from the back, or a combination of both. By choosing the option with the minimum deletions, you ensure an optimal solution.

Efficient Calculation of Deletions

You can find the positions of the minimum and maximum elements, then calculate the number of deletions by considering the left and right sections of the array. The goal is to minimize the number of elements removed while ensuring both the min and max are deleted.

Consider Edge Cases

Edge cases include scenarios where the array only contains one element or when the min and max elements are at the same position. Handling these cases efficiently ensures the solution works across all valid inputs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the array. This is because we need to find the positions of the minimum and maximum elements, which takes linear time. The space complexity is O(1), as we are only using a few extra variables to store the indices of the min and max elements.

What Interviewers Usually Probe

The candidate shows an understanding of greedy algorithms and how they apply to array manipulation.
The candidate considers multiple approaches to minimize deletions and effectively handles edge cases.
The candidate optimizes the solution for both time and space complexity while clearly explaining their approach.

Common Pitfalls or Variants

Common pitfalls

The candidate might overlook edge cases where the array only contains one element, or where the min and max elements are at the same position.
Failing to account for the scenario where deletions must come from both ends of the array could lead to suboptimal solutions.
Not validating the array’s size or handling out-of-bounds scenarios efficiently could result in runtime errors.

Follow-up variants

The problem could be modified to allow removing elements only from one side of the array (front or back).
An extension of this problem could involve keeping track of the deleted elements in addition to the deletions themselves.
A more complex variant might involve removing the minimum and maximum while ensuring the remaining elements maintain a specific order.

FAQ

What is the primary pattern for solving the 'Removing Minimum and Maximum From Array' problem?

The primary pattern is greedy choice combined with invariant validation. You calculate deletions for all possible approaches and select the one with the minimum deletions.

How do I handle edge cases in the 'Removing Minimum and Maximum From Array' problem?

Edge cases include arrays with only one element or arrays where the minimum and maximum are at the same position. Ensure you handle these efficiently to avoid errors.

What is the time complexity of the 'Removing Minimum and Maximum From Array' problem?

The time complexity is O(n), where n is the length of the array, since you need to find the positions of the minimum and maximum elements.

Can the solution be optimized further for space complexity?

Yes, the solution is already space-efficient with a space complexity of O(1), as it only requires a few variables to store indices.

What if I can only delete elements from one side of the array?

In such a case, you would need to adjust your approach to consider deletions from only the front or the back, which would change the solution's efficiency.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        mi = mx = 0
        for i, num in enumerate(nums):
            if num < nums[mi]:
                mi = i
            if num > nums[mx]:
                mx = i
        if mi > mx:
            mi, mx = mx, mi
        return min(mx + 1, len(nums) - mi, mi + 1 + len(nums) - mx)

Continue Practicing

#2087 minimum cost homecoming of a robot in a grid #2078 two furthest houses with different colors #2071 maximum number of tasks you can assign