LeetCode 2091 - Removing Minimum and Maximum From Array

LeetCode Problem 2091

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us a 0-indexed array of distinct integers. Among these integers, exactly one value is the smallest element in the array, and exactly one value is the largest element in the array. The task is to remove both of these elements using the fewest deletions possible.

A deletion operation is very restricted. We are only allowed to remove elements from either:

• the front of the array
• the back of the array

We cannot remove an element directly from the middle. Every deletion shrinks the array, and the remaining elements shift accordingly.

The goal is to compute the minimum number of deletions needed so that both the minimum and maximum elements have been removed from the array.

The constraints tell us several important things:

• The array can contain up to 10^5 elements, so inefficient brute-force simulation approaches can become too slow.
• All numbers are distinct, which guarantees there is exactly one minimum and exactly one maximum.
• Values may be negative, positive, or zero, but only their relative ordering matters.

An important detail is that removing one element may also move the position of the other element relative to the array ends. Because deletions can only occur at the front or back, the problem is fundamentally about choosing the cheapest way to expose and remove both target elements.

Several edge cases are important:

• The array may contain only one element. In that case, the single element is both the minimum and maximum.
• The minimum and maximum may both be near the front.
• The minimum and maximum may both be near the back.
• One may be near the front while the other is near the back.
• The minimum index might appear after the maximum index, so careful index normalization helps simplify calculations.

Approaches

Brute Force Approach

A brute-force strategy would attempt to simulate every possible sequence of deletions from the front and back. At each step, we could choose either side and continue until both the minimum and maximum elements are removed.

This approach is correct because it explores all possible valid deletion sequences and therefore eventually finds the minimum number of operations.

However, this method becomes extremely inefficient. Each deletion creates two branching possibilities, leading to exponential growth in the number of states. Even with memoization, repeatedly constructing or tracking array states would still be unnecessarily expensive for arrays of size up to 10^5.

Because the deletion rules are highly structured, we can do much better by analyzing positions directly instead of simulating deletions.

Optimal Greedy Observation

The key insight is that only the positions of the minimum and maximum elements matter.

Suppose:

• minIndex is the position of the minimum element
• maxIndex is the position of the maximum element

There are only three meaningful strategies:

1. Remove both from the front.
2. Remove both from the back.
3. Remove one from the front and the other from the back.

No other strategy can outperform these because deletions only happen at array boundaries.

To simplify reasoning, we first reorder the indices so that:

• left = min(minIndex, maxIndex)
• right = max(minIndex, maxIndex)

Now the three possible costs become:

1. Remove both from the front:

• Need right + 1 deletions.

2. Remove both from the back:

• Need n - left deletions.

3. Remove one from each side:

• Remove up to left from the front.
• Remove up to right from the back.
• Total deletions:

left + 1 + (n - right)

The minimum of these three values is the answer.

This works in linear time because we only scan the array once to locate the minimum and maximum elements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Simulates all deletion sequences
Optimal	O(n)	O(1)	Uses index analysis and evaluates only three cases

Algorithm Walkthrough

1. Traverse the array once to locate the indices of the minimum and maximum elements.

During the scan:

• Track the smallest value and its index.
• Track the largest value and its index.

2. Normalize the indices.

Let:

• left = min(minIndex, maxIndex)
• right = max(minIndex, maxIndex)

This guarantees left <= right, which simplifies later calculations. 3. Compute the cost of removing both elements from the front.

If we repeatedly delete from the front, we must continue until the farther target element is removed.

Since right is farther from the front:

• deletions needed = right + 1

4. Compute the cost of removing both elements from the back.

If we repeatedly delete from the back, we must continue until the farther target element from the back is removed.

Since left is farther from the back:

• deletions needed = n - left

5. Compute the mixed strategy.

Remove:

• the left target from the front
• the right target from the back

Cost:

• front deletions = left + 1
• back deletions = n - right

Total:

• left + 1 + (n - right)

6. Return the minimum among the three computed costs.

Why it works

Every valid solution must eventually remove both target indices. Since deletions can only happen from array ends, the only meaningful possibilities are:

• both removed from the front
• both removed from the back
• one removed from each side

The algorithm evaluates the exact cost of each scenario and chooses the smallest one. Because these cases exhaust all optimal possibilities, the minimum among them is guaranteed to be the correct answer.

Python Solution

from typing import List

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        n = len(nums)

        min_index = 0
        max_index = 0

        for i in range(n):
            if nums[i] < nums[min_index]:
                min_index = i

            if nums[i] > nums[max_index]:
                max_index = i

        left = min(min_index, max_index)
        right = max(min_index, max_index)

        remove_front = right + 1
        remove_back = n - left
        remove_both_sides = (left + 1) + (n - right)

        return min(remove_front, remove_back, remove_both_sides)

The implementation begins by scanning the array once to locate the indices of the minimum and maximum elements. Instead of sorting or using extra data structures, the algorithm maintains two indices while iterating through the array.

After locating the indices, the code normalizes them into left and right. This makes the later formulas consistent regardless of whether the minimum appears before or after the maximum.

The next section computes the three possible deletion strategies:

• removing everything from the front until both are deleted
• removing everything from the back until both are deleted
• combining front and back deletions

Finally, the smallest value among these three possibilities is returned.

The implementation uses constant extra memory and only performs one pass through the array.

Go Solution

func minimumDeletions(nums []int) int {
	n := len(nums)

	minIndex := 0
	maxIndex := 0

	for i := 0; i < n; i++ {
		if nums[i] < nums[minIndex] {
			minIndex = i
		}

		if nums[i] > nums[maxIndex] {
			maxIndex = i
		}
	}

	left := min(minIndex, maxIndex)
	right := max(minIndex, maxIndex)

	removeFront := right + 1
	removeBack := n - left
	removeBothSides := (left + 1) + (n - right)

	return min(removeFront, min(removeBack, removeBothSides))
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows exactly the same logic as the Python solution. Since Go does not provide built-in min and max functions for integers, helper functions are defined manually.

The solution uses only integer arithmetic, so overflow is not a concern under the given constraints. Slices are used directly without any copying, keeping the space complexity constant.

Worked Examples

Example 1

Input:

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

Step 1: Find minimum and maximum

Index	Value	Current Min Index	Current Max Index
0	2	0	0
1	10	0	1
2	7	0	1
3	5	0	1
4	4	0	1
5	1	5	1
6	8	5	1
7	6	5	1

Final values:

• minIndex = 5
• maxIndex = 1

Normalize:

• left = 1
• right = 5

Step 2: Compute strategies

Strategy	Formula	Result
Front only	right + 1	6
Back only	n - left	7
Both sides	(left + 1) + (n - right)	2 + 3 = 5

Minimum answer:

5

Example 2

Input:

nums = [0,-4,19,1,8,-2,-3,5]

Step 1: Find minimum and maximum

• Minimum value = -4
• minIndex = 1
• Maximum value = 19
• maxIndex = 2

Normalize:

• left = 1
• right = 2

Step 2: Compute strategies

Strategy	Formula	Result
Front only	right + 1	3
Back only	n - left	7
Both sides	(left + 1) + (n - right)	2 + 6 = 8

Minimum answer:

3

Example 3

Input:

nums = [101]

Step 1: Find minimum and maximum

Both minimum and maximum are at index 0.

Normalize:

• left = 0
• right = 0

Step 2: Compute strategies

Strategy	Formula	Result
Front only	1	1
Back only	1	1
Both sides	1 + 1	2

Minimum answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One linear scan to locate minimum and maximum indices
Space	O(1)	Only a few variables are used

The algorithm processes each array element exactly once. All later computations are constant time arithmetic operations. No auxiliary data structures proportional to input size are allocated, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        n = len(nums)

        min_index = 0
        max_index = 0

        for i in range(n):
            if nums[i] < nums[min_index]:
                min_index = i

            if nums[i] > nums[max_index]:
                max_index = i

        left = min(min_index, max_index)
        right = max(min_index, max_index)

        return min(
            right + 1,
            n - left,
            (left + 1) + (n - right)
        )

sol = Solution()

assert sol.minimumDeletions([2,10,7,5,4,1,8,6]) == 5  # provided example 1
assert sol.minimumDeletions([0,-4,19,1,8,-2,-3,5]) == 3  # provided example 2
assert sol.minimumDeletions([101]) == 1  # single element array

assert sol.minimumDeletions([1,2]) == 2  # min at front, max at back
assert sol.minimumDeletions([2,1]) == 2  # max at front, min at back

assert sol.minimumDeletions([1,5,3,4,2]) == 2  # both removable from front
assert sol.minimumDeletions([3,2,1,4]) == 2  # one from each side

assert sol.minimumDeletions([5,4,3,2,1]) == 2  # both near back
assert sol.minimumDeletions([1,2,3,4,5]) == 2  # both near opposite ends

assert sol.minimumDeletions([-10,-20,-30,-5]) == 2  # negative numbers
assert sol.minimumDeletions([100000,-100000]) == 2  # constraint extremes

assert sol.minimumDeletions([7,1,2,3,4,5,6,8]) == 2  # min near front, max at end
assert sol.minimumDeletions([8,2,3,4,5,6,1,7]) == 3  # mixed deletion strategy best

Test	Why
[2,10,7,5,4,1,8,6]	Validates mixed front and back strategy
[0,-4,19,1,8,-2,-3,5]	Validates removing both from front
[101]	Tests single-element edge case
[1,2]	Smallest non-trivial array
[2,1]	Reversed two-element array
[1,5,3,4,2]	Both targets near front
[3,2,1,4]	Optimal mixed strategy
[5,4,3,2,1]	Both targets near back
[1,2,3,4,5]	Targets at opposite ends
[-10,-20,-30,-5]	Handles negative numbers
[100000,-100000]	Constraint boundary values
[7,1,2,3,4,5,6,8]	Minimum near front, maximum at end
[8,2,3,4,5,6,1,7]	Mixed deletions outperform single-side removal

Edge Cases

Single Element Array

When the array contains only one element, that element is simultaneously the minimum and maximum. A buggy implementation might incorrectly count two removals because it treats the minimum and maximum independently.

The implementation handles this naturally because both indices become 0, and the minimum among the computed strategies is correctly 1.

Minimum and Maximum at Opposite Ends

Consider an array like:

[1, 2, 3, 4, 5]

The minimum is at the front and the maximum is at the back. A naive strategy that removes from only one side would require deleting the entire array.

The mixed strategy correctly identifies that removing one element from the front and one from the back costs only 2.

Minimum Appears After Maximum

The minimum index is not guaranteed to be smaller than the maximum index. For example:

[10, 3, 2, 1]

Here:

• maximum index = 0
• minimum index = 3

Without normalizing the indices, formulas can become error-prone and inconsistent.

The implementation solves this by introducing:

left = min(min_index, max_index)
right = max(min_index, max_index)

This guarantees a consistent ordering and simplifies all subsequent calculations.

Both Targets Near the Same Side

Consider:

[1, 5, 4, 3, 2]

Both the minimum and maximum are near the front. A buggy implementation might always consider mixed deletions even when unnecessary.

The algorithm explicitly computes all three possibilities and chooses the smallest one, ensuring the optimal same-side strategy is selected automatically.