# Removing Minimum and Maximum From Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/removing-minimum-and-maximum-from-array)
Canonical: https://scaleengineer.com/dsa/problems/removing-minimum-and-maximum-from-array
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## 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._

**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**.

# Approaches
## Sorting-Based Approach
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.
**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.
**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.
### Explanation
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:
1.  **Remove from Front:** Remove both elements by deleting from the front of the array. The number of deletions would be `max(minIndex, maxIndex) + 1`.
2.  **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.
3.  **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.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int minimumDeletions(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return n;
        }

        int[][] indexedNums = new int[n][2];
        for (int i = 0; i < n; i++) {
            indexedNums[i][0] = nums[i];
            indexedNums[i][1] = i;
        }

        Arrays.sort(indexedNums, Comparator.comparingInt(a -> a[0]));

        int minIndex = indexedNums[0][1];
        int maxIndex = indexedNums[n - 1][1];

        int left = Math.min(minIndex, maxIndex);
        int right = Math.max(minIndex, maxIndex);

        // Case 1: Remove both from the front
        int deletions1 = right + 1;

        // Case 2: Remove both from the back
        int deletions2 = n - left;

        // Case 3: Remove one from front, one from back
        int deletions3 = (left + 1) + (n - right);

        return Math.min(deletions1, Math.min(deletions2, deletions3));
    }
}
```
### 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))`.

## Single-Pass Linear Scan
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.
**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.
**Pros:** Optimal time complexity.; Optimal space complexity.; Simple and efficient implementation.
**Cons:** None, this is the best possible solution.
### Explanation
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:
1.  **Remove from Front:** Deleting from the front until the furthest of the two elements (`max(minIndex, maxIndex)`) is removed. Cost: `max(minIndex, maxIndex) + 1`.
2.  **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)`.
3.  **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.

```java
class Solution {
    public int minimumDeletions(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return n;
        }

        int minIndex = 0;
        int maxIndex = 0;

        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        int left = Math.min(minIndex, maxIndex);
        int right = Math.max(minIndex, maxIndex);

        // Case 1: Remove both from the front
        int deletions1 = right + 1;

        // Case 2: Remove both from the back
        int deletions2 = n - left;

        // Case 3: Remove one from front, one from back
        int deletions3 = (left + 1) + (n - right);

        return Math.min(deletions1, Math.min(deletions2, deletions3));
    }
}
```
### 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))`.

# Solutions
### Java

```java
class Solution {
public
  int minimumDeletions(int[] nums) {
    int mi = 0, mx = 0, n = nums.length;
    for (int i = 0; i < n; ++i) {
      if (nums[i] < nums[mi]) {
        mi = i;
      }
      if (nums[i] > nums[mx]) {
        mx = i;
      }
    }
    if (mi > mx) {
      int t = mx;
      mx = mi;
      mi = t;
    }
    return Math.min(Math.min(mx + 1, n - mi), mi + 1 + n - mx);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumDeletions(vector<int> &nums) {
    int mi = 0, mx = 0, n = nums.size();
    for (int i = 0; i < n; ++i) {
      if (nums[i] < nums[mi])
        mi = i;
      if (nums[i] > nums[mx])
        mx = i;
    }
    if (mi > mx) {
      int t = mi;
      mi = mx;
      mx = t;
    }
    return min(min(mx + 1, n - mi), mi + 1 + n - mx);
  }
};

```

### Python

```python
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)

```