Watch 10 video solutions for Removing Minimum and Maximum From Array, a medium level problem involving Array, Greedy. This walkthrough by Aditya Rajiv has 3,600 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105nums are distinct.Problem Overview: You receive an integer array and must remove both the minimum and maximum values using the fewest deletions. Deletions can only occur from the front or the back of the array, so the task reduces to choosing the best sequence of prefix and/or suffix removals.
Approach 1: Calculate Minimum Deletions from Three Possible Strategies (Time: O(n), Space: O(1))
First scan the array to locate the indices of the minimum and maximum values. Once you know their positions, three deletion strategies exist: remove elements only from the front, only from the back, or from both ends. If the smaller index is left and the larger index is right, the options become right + 1 deletions from the front, n - left deletions from the back, or a mixed strategy of (left + 1) + (n - right). Compute all three and return the minimum. The approach works because the order of deletions does not matter once both indices are known. This is the most direct greedy formulation of the problem and only requires a single traversal to find the min and max positions.
Approach 2: Single Pass Minimization of Deletions (Time: O(n), Space: O(1))
This variation combines index discovery and deletion calculation into a single scan. As you iterate through the array, update the current positions of the minimum and maximum elements. After each update, compute the potential deletion counts using the same three strategies (front, back, both sides) and track the smallest value seen so far. The key idea is incremental evaluation instead of waiting until the end of the scan. The algorithm still relies on the same greedy insight: once the positions of min and max are known, the optimal removal must be one of the three boundary strategies. Since only a few integers are stored, the space usage stays constant.
Recommended for interviews: The three-strategy greedy solution is what most interviewers expect. It clearly demonstrates reasoning about boundary operations in an array and reduces the problem to a small set of deterministic cases. Explaining why only three deletion strategies exist shows strong problem decomposition skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Three Strategy Greedy Calculation | O(n) | O(1) | General case. Clear reasoning and easiest to explain in interviews. |
| Single Pass Minimization | O(n) | O(1) | When combining scanning and evaluation in one traversal for slightly cleaner runtime flow. |