Removing Minimum and Maximum From Array

Med

#1903Time: O(N log N) due to the sorting step. Creating the indexed array takes `O(N)`, sorting takes `O(N log N)`, and the final calculations take `O(1)`. The dominant factor is sorting.Space: O(N) to store the auxiliary `indexedNums` array.

Patterns

Greedy

Data structures

Array

Prompt

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵
The integers in nums are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves sorting the array to find the minimum and maximum elements. By sorting, the minimum element will be the first element and the maximum will be the last. However, we need their original indices. To preserve the original indices, we can create a helper data structure (like an array of pairs or objects) that stores both the value and its original index. After sorting this structure, we can easily retrieve the original indices of the minimum and maximum values and then calculate the minimum deletions required.

Algorithm

Handle the edge case where the array has only one element. If nums.length == 1, return 1.
Create a 2D array or an array of custom objects indexedNums of size n x 2 to store [value, original_index].
Iterate through the input array nums and populate indexedNums. For each i, set indexedNums[i] = {nums[i], i}.
Sort indexedNums based on the values (the first element of the pair).
The original index of the minimum element is minIndex = indexedNums[0][1].
The original index of the maximum element is maxIndex = indexedNums[n-1][1].
Define left = min(minIndex, maxIndex) and right = max(minIndex, maxIndex).
Calculate the deletions for the three cases:
- case1 = right + 1 (deleting both from the front)
- case2 = n - left (deleting both from the back)
- case3 = (left + 1) + (n - right) (deleting one from each end)
Return min(case1, min(case2, case3)).

Walkthrough

The core idea is to find the indices of the minimum and maximum elements by sorting. Since sorting the original array would lose the index information, we first create an auxiliary array of pairs, where each pair contains an element from the input array and its original index.

We then sort this auxiliary array based on the element values. After sorting, the first element of the auxiliary array will correspond to the minimum value of the original array, and the last element will correspond to the maximum value.

From these two pairs, we extract their original indices. Let's call them minIndex and maxIndex.

With minIndex and maxIndex found, we can determine the minimum number of deletions. There are three possible scenarios to remove both elements:

Remove from Front: Remove both elements by deleting from the front of the array. The number of deletions would be max(minIndex, maxIndex) + 1.
Remove from Back: Remove both elements by deleting from the back of the array. The number of deletions would be n - min(minIndex, maxIndex), where n is the length of the array.
Remove from Both Ends: Remove one element from the front and the other from the back. The number of deletions would be (min(minIndex, maxIndex) + 1) + (n - max(minIndex, maxIndex)).

The final answer is the minimum of the deletions calculated in these three scenarios.

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public int minimumDeletions(int[] nums) {6        int n = nums.length;7        if (n <= 1) {8            return n;9        }10 11        int[][] indexedNums = new int[n][2];12        for (int i = 0; i < n; i++) {13            indexedNums[i][0] = nums[i];14            indexedNums[i][1] = i;15        }16 17        Arrays.sort(indexedNums, Comparator.comparingInt(a -> a[0]));18 19        int minIndex = indexedNums[0][1];20        int maxIndex = indexedNums[n - 1][1];21 22        int left = Math.min(minIndex, maxIndex);23        int right = Math.max(minIndex, maxIndex);24 25        // Case 1: Remove both from the front26        int deletions1 = right + 1;27 28        // Case 2: Remove both from the back29        int deletions2 = n - left;30 31        // Case 3: Remove one from front, one from back32        int deletions3 = (left + 1) + (n - right);33 34        return Math.min(deletions1, Math.min(deletions2, deletions3));35    }36}

Complexity

Time

O(N log N) due to the sorting step. Creating the indexed array takes `O(N)`, sorting takes `O(N log N)`, and the final calculations take `O(1)`. The dominant factor is sorting.

Space

O(N) to store the auxiliary `indexedNums` array.

Trade-offs

Pros

Conceptually straightforward if one is familiar with sorting.
Correctly solves the problem.

Cons

Not the most efficient solution in terms of time and space complexity.
Requires extra space, which can be significant for large arrays.

This is the most efficient approach. It involves iterating through the array just once to find the indices of the minimum and maximum elements. By maintaining variables to track the minimum value, maximum value, and their respective indices during a single pass, we can avoid the overhead of sorting. Once the indices are found, we use the same logic as the previous approach to calculate the minimum number of deletions based on the three possible removal strategies.

Algorithm

Handle the edge case where the array has one or zero elements. If nums.length <= 1, return nums.length.
Initialize minIndex = 0 and maxIndex = 0.
Iterate through the array nums from i = 0 to n-1.
Inside the loop, if nums[i] < nums[minIndex], update minIndex = i.
If nums[i] > nums[maxIndex], update maxIndex = i.
After the loop, define left = min(minIndex, maxIndex) and right = max(minIndex, maxIndex).
Calculate the deletions for the three cases:
- case1 = right + 1 (deleting both from the front)
- case2 = n - left (deleting both from the back)
- case3 = (left + 1) + (n - right) (deleting one from each end)
Return min(case1, min(case2, case3)).

Walkthrough

The key to optimizing the problem is to find the indices of the minimum and maximum elements in linear time. This can be achieved with a single pass through the array.

We initialize variables to store the minimum and maximum element's indices, typically using the first element of the array.

We then iterate through the rest of the array. For each element, we compare it with the current minimum and maximum values. If the current element is smaller than the tracked minimum, we update the minimum's index. Similarly, if it's larger than the tracked maximum, we update the maximum's index.

After this single pass is complete, we will have the exact indices of the overall minimum and maximum elements in the array.

With these indices, minIndex and maxIndex, we analyze the three scenarios for removal:

Remove from Front: Deleting from the front until the furthest of the two elements (max(minIndex, maxIndex)) is removed. Cost: max(minIndex, maxIndex) + 1.
Remove from Back: Deleting from the back until the nearest of the two elements to the front (min(minIndex, maxIndex)) is removed. Cost: n - min(minIndex, maxIndex).
Remove from Both Ends: Deleting from the front to remove the element with the smaller index, and from the back to remove the element with the larger index. Cost: (min(minIndex, maxIndex) + 1) + (n - max(minIndex, maxIndex)).

The minimum of these three costs is the answer.

1class Solution {2    public int minimumDeletions(int[] nums) {3        int n = nums.length;4        if (n <= 1) {5            return n;6        }7 8        int minIndex = 0;9        int maxIndex = 0;10 11        for (int i = 0; i < n; i++) {12            if (nums[i] < nums[minIndex]) {13                minIndex = i;14            }15            if (nums[i] > nums[maxIndex]) {16                maxIndex = i;17            }18        }19 20        int left = Math.min(minIndex, maxIndex);21        int right = Math.max(minIndex, maxIndex);22 23        // Case 1: Remove both from the front24        int deletions1 = right + 1;25 26        // Case 2: Remove both from the back27        int deletions2 = n - left;28 29        // Case 3: Remove one from front, one from back30        int deletions3 = (left + 1) + (n - right);31 32        return Math.min(deletions1, Math.min(deletions2, deletions3));33    }34}

Complexity

Time

O(N) because we iterate through the array once to find the indices of the minimum and maximum elements. The subsequent calculations are O(1).

Space

O(1) as we only use a few variables to store indices, regardless of the input array size.

Trade-offs

Pros

Optimal time complexity.
Optimal space complexity.
Simple and efficient implementation.

Cons

None, this is the best possible solution.

Solutions

Solution

1class Solution {2public3  int minimumDeletions(int[] nums) {4    int mi = 0, mx = 0, n = nums.length;5    for (int i = 0; i < n; ++i) {6      if (nums[i] < nums[mi]) {7        mi = i;8      }9      if (nums[i] > nums[mx]) {10        mx = i;11      }12    }13    if (mi > mx) {14      int t = mx;15      mx = mi;16      mi = t;17    }18    return Math.min(Math.min(mx + 1, n - mi), mi + 1 + n - mx);19  }20}

1class Solution {2public:3  int minimumDeletions(vector<int> &nums) {4    int mi = 0, mx = 0, n = nums.size();5    for (int i = 0; i < n; ++i) {6      if (nums[i] < nums[mi])7        mi = i;8      if (nums[i] > nums[mx])9        mx = i;10    }11    if (mi > mx) {12      int t = mi;13      mi = mx;14      mx = t;15    }16    return min(min(mx + 1, n - mi), mi + 1 + n - mx);17  }18};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem