Problem Description

You have an array nums containing distinct integers at different positions (0-indexed). Your task is to remove both the minimum and maximum values from this array.

You can only remove elements in two ways:

• Delete from the front of the array (removing the first element)
• Delete from the back of the array (removing the last element)

You need to find the minimum number of deletions required to remove both the smallest and largest elements from the array.

For example, if you have an array like [2, 10, 7, 5, 4, 1, 8, 6]:

• The minimum value is 1 (at index 5)
• The maximum value is 10 (at index 1)

You could remove them by:

• Deleting from the front until both are removed (6 deletions)
• Deleting from the back until both are removed (7 deletions)
• Deleting from both ends strategically (2 from front to get 10, then 3 from back to get 1, totaling 5 deletions)

The solution finds the positions of both minimum and maximum elements, then calculates three possible strategies:

1. Delete everything from the front up to and including the rightmost target element
2. Delete everything from the back up to and including the leftmost target element
3. Delete from the front to get one element and from the back to get the other

The answer is the minimum among these three approaches.

Intuition

Since we need to remove both the minimum and maximum elements, and we can only delete from the front or back, we need to think about where these two elements are positioned in the array.

The key insight is that there are only three reasonable strategies to remove both elements:

1. Delete only from the front: Keep deleting from the front until both elements are gone. This means we delete up to the position of whichever element is further from the front.

2. Delete only from the back: Keep deleting from the back until both elements are gone. This means we delete up to the position of whichever element is further from the back.

3. Delete from both ends: Delete from the front to remove one element, and from the back to remove the other. This works best when one element is closer to the front and the other is closer to the back.

Let's visualize this with positions. If we have the minimum at position mi and maximum at position mx, and assume mi < mx (the left one comes first), then:

• Strategy 1: Delete mx + 1 elements from the front (since we need to reach index mx)
• Strategy 2: Delete len(nums) - mi elements from the back (to reach index mi from the back)
• Strategy 3: Delete mi + 1 from the front to get the minimum, plus len(nums) - mx from the back to get the maximum

The optimal solution is simply the minimum of these three values. By ensuring mi < mx through swapping if needed, we can consistently apply these formulas regardless of which element (min or max) appears first in the array.

This greedy approach works because once we commit to a deletion strategy, we want to minimize the total deletions needed to reach both target elements.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a straightforward approach with these steps:

Step 1: Find the indices of minimum and maximum elements

We iterate through the array once, keeping track of the indices of the minimum and maximum values:

mi = mx = 0
for i, num in enumerate(nums):
    if num < nums[mi]:
        mi = i
    if num > nums[mx]:
        mx = i

This uses two variables mi and mx to store the indices. We compare each element with the current minimum and maximum values and update the indices accordingly.

Step 2: Ensure the minimum index comes before the maximum index

For consistency in our calculations, we swap the indices if needed:

if mi > mx:
    mi, mx = mx, mi

After this swap, mi represents the leftmost target element's index, and mx represents the rightmost target element's index.

Step 3: Calculate the minimum deletions using three strategies

We compute the cost of each strategy and return the minimum:

return min(mx + 1, len(nums) - mi, mi + 1 + len(nums) - mx)

Breaking down the three strategies:

• mx + 1: Delete from the front until we reach the rightmost target (index mx). We need mx + 1 deletions since arrays are 0-indexed.
• len(nums) - mi: Delete from the back until we reach the leftmost target (index mi). The number of elements from index mi to the end is len(nums) - mi.
• mi + 1 + len(nums) - mx: Delete from both ends - remove the leftmost target from the front (mi + 1 deletions) and the rightmost target from the back (len(nums) - mx deletions).

Time Complexity: O(n) where n is the length of the array, as we traverse it once to find min and max indices.

Space Complexity: O(1) as we only use a constant amount of extra space for storing indices.

Example Walkthrough

Let's walk through the solution with a concrete example: nums = [5, 3, 8, 1, 9, 2]

Step 1: Find minimum and maximum elements

• Traverse the array to locate:
  • Minimum value: 1 at index 3
  • Maximum value: 9 at index 4

So mi = 3 and mx = 4.

Step 2: Ensure correct ordering Since mi < mx (3 < 4), no swap is needed. We have:

• Leftmost target at index 3
• Rightmost target at index 4

Step 3: Calculate three strategies

Let's visualize the array with our targets marked:

[5, 3, 8, 1, 9, 2]
          ↑  ↑
         mi  mx

Now we calculate each strategy:

Strategy 1 - Delete only from front:

• Need to reach index 4 (the rightmost target)
• Deletions required: mx + 1 = 4 + 1 = 5
• Process: Delete [5], [3], [8], [1], [9] → Array becomes [2]

Strategy 2 - Delete only from back:

• Need to reach index 3 (the leftmost target) from the back
• Deletions required: len(nums) - mi = 6 - 3 = 3
• Process: Delete [2], [9], [1] → Array becomes [5, 3, 8]

Strategy 3 - Delete from both ends:

• Delete from front to reach index 3: mi + 1 = 3 + 1 = 4 deletions
• Delete from back to reach index 4: len(nums) - mx = 6 - 4 = 2 deletions
• Total: 4 + 2 = 6 deletions
• Process: Delete [5], [3], [8], [1] from front, then [2], [9] from back → Array becomes empty

Final Answer: min(5, 3, 6) = 3

The optimal strategy is to delete only from the back, requiring just 3 deletions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

• The code iterates through the array once using enumerate(nums) to find the indices of the minimum and maximum elements, which takes O(n) time
• The swap operation mi, mx = mx, mi takes O(1) time
• The final calculation with min() comparing three values takes O(1) time
• Overall time complexity is O(n) where n is the length of the input array

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space
• Variables mi, mx, i, and num are the only additional variables created
• No additional data structures are used that scale with input size
• The space complexity is O(1) - constant space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Single Element Arrays

While the given solution handles single element arrays correctly (when n=1, all three strategies return 1), developers might overcomplicate this edge case or add unnecessary special handling.

Why it works: When the array has only one element, both min and max indices are 0, so:

• Strategy 1: 0 + 1 = 1
• Strategy 2: 1 - 0 = 1
• Strategy 3: 0 + 1 + 1 - 0 = 2 The minimum is 1, which is correct.

2. Incorrectly Calculating Deletions from the Back

A common mistake is using n - mi - 1 instead of n - mi when calculating deletions from the back.

Incorrect:

return min(mx + 1, len(nums) - mi - 1, mi + 1 + len(nums) - mx - 1)

Correct:

return min(mx + 1, len(nums) - mi, mi + 1 + len(nums) - mx)

Why: To delete from the back until index i is removed, we need to delete n - i elements, not n - i - 1.

3. Not Swapping Indices When Necessary

Some developers might assume the minimum element always appears before the maximum element in the array, leading to incorrect calculations.

Problem Example: In array [5, 1, 3, 9, 2], the minimum (1) is at index 1, and the maximum (9) is at index 3. Without swapping, the logic is straightforward.

But in array [5, 9, 3, 1, 2], the minimum (1) is at index 3, and the maximum (9) is at index 1. Without ensuring mi < mx, the third strategy calculation becomes confusing.

Solution: Always normalize by swapping so that mi represents the leftmost target and mx represents the rightmost target:

if min_index > max_index:
    min_index, max_index = max_index, min_index

4. Overthinking When Min and Max Are the Same Element

In arrays where all elements are identical (though the problem states "distinct integers"), or conceptually when thinking about the algorithm, developers might add special cases.

Reality: The algorithm naturally handles this case. If min and max are at the same index, all three strategies will correctly calculate the deletions needed to remove that single element.

5. Using Wrong Variable Names Leading to Logic Errors

Using ambiguous names like left and right instead of min_index and max_index can cause confusion about what these variables represent, especially after swapping.

Better Practice: Use descriptive names that clearly indicate what the variable represents throughout the algorithm's execution.