Removing Minimum and Maximum From Array

Removing Minimum and Maximum From Array

What is this problem about?

The Removing Minimum and Maximum From Array interview question gives you an array of distinct integers. You must find both the minimum and maximum elements and remove both of them. The only allowed operation is removing elements from the front or back of the array (you cannot remove from the middle directly). You must find the minimum number of such front/back deletion moves to eliminate both the minimum and the maximum.

Why is this asked in interviews?

Amazon asks this problem because it tests greedy enumeration on array boundaries. Candidates must recognize that for each target element (the min and the max), it can only be reached by deleting from the left or from the right. This creates four combinations to consider: delete both from left, both from right, min from left and max from right, or min from right and max from left. Taking the minimum across these four strategies is the solution.

Algorithmic pattern used

The pattern is greedy enumeration of boundary strategies. Let n be the array length, min_idx the index of the minimum, and max_idx the index of the maximum. Define:

• left(i) = cost to remove element at index i from the left = i + 1.
• right(i) = cost to remove element at index i from the right = n - i.

Four strategies:

1. Both from left: max(left(min_idx), left(max_idx))
2. Both from right: max(right(min_idx), right(max_idx))
3. Min from left, max from right: left(min_idx) + right(max_idx)
4. Min from right, max from left: right(min_idx) + left(max_idx)

Return the minimum across all four.

Example explanation

Array: [2, 10, 7, 5, 4, 1, 8, 6]. Min = 1 at index 5. Max = 10 at index 1.

• Both left: max(6, 2) = 6.
• Both right: max(3, 7) = 7.
• Min left, Max right: 6 + 7 = 13.
• Min right, Max left: 3 + 2 = 5.

Minimum: 5.

Common mistakes candidates make

• Considering only "both from left" and "both from right" and missing the cross strategies.
• Computing left cost as i instead of i + 1 (off-by-one — removing element at index i requires deleting i+1 elements).
• Not swapping min_idx and max_idx to ensure consistent strategy calculation when max appears before min.
• Forgetting that when one element is covered by the other strategy's sweep, only the max of the two individual costs matters.

Interview preparation tip

For the Removing Minimum and Maximum From Array coding problem, the array and greedy interview pattern relies on enumerating all four boundary strategies and taking the minimum. Draw a simple diagram with the positions of min and max before coding. Amazon interviewers appreciate clean variable naming (left_cost, right_cost) over complex index arithmetic inline. Practice the edge case where min and max are adjacent at the very ends of the array.