Removing Minimum and Maximum From Array — Problem & Solution
Removing Minimum and Maximum From Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Removing Minimum and Maximum From Array is a medium coding problem on arrays and greedy, asked in Amazon, Microsoft and Zoho interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Microsoft, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums holds distinct integers. One deletion removes the element at the front or the back of the array.
Return the minimum number of deletions needed to remove both the minimum and the maximum element.
Example 1
Input: nums = [2,10,7,5,4,1,8,6]
Output: 5
Explanation: The max 10 is at index 1 and the min 1 at index 5: take 2 from the front and 3 from the back.
Example 2
Input: nums = [0,-4,19,1,8,-2,-3,5]
Output: 3
Explanation: The max 19 is at index 2, so three deletions from the front cover both.
Example 3
Input: nums = [101]
Output: 1
Constraints
1 <= nums.length <= 100000-100000 <= nums[i] <= 100000All values in nums are distinct.
Hints for Removing Minimum and Maximum From Array
Hint 1
Only the two positions matter: where the minimum sits and where the maximum sits.
Hint 2
There are exactly three strategies — both from the front, both from the back, or one from each end.
Hint 3
Take the cheapest of the three.
How to solve Removing Minimum and Maximum From Array
Find the two indices, then compare the only three ways to reach them from the ends. Everything else about the array is irrelevant.
Approach
- Locate the index of the minimum and of the maximum; let
loandhibe the smaller and larger of the two. - Both from the front costs
hi + 1; both from the back costsn - lo; one from each end costs(lo + 1) + (n - hi). - Return the minimum of the three.
Why it works
Deletions only ever come from the ends, so removing an element at index i from the front costs i + 1 and from the back costs n - i. Both targets must be removed, and each is taken from one end or the other — which is exactly the three cases, since taking the further one from an end automatically removes the nearer one on that side.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Forgetting the mixed strategy loses cases like the first example.
- In the mixed case the front takes the earlier index and the back the later one, never the other way round.
- A single-element array needs one deletion, since the minimum and maximum coincide.
Reference solution
Python
from typing import List
def minimumDeletions(nums: List[int]) -> int:
n = len(nums)
mi = nums.index(min(nums))
ma = nums.index(max(nums))
lo, hi = min(mi, ma), max(mi, ma)
return min(hi + 1, n - lo, lo + 1 + (n - hi))Java
public static int minimumDeletions(int[] nums) {
int n = nums.length, mi = 0, ma = 0;
for (int i = 1; i < n; i++) {
if (nums[i] < nums[mi]) mi = i;
if (nums[i] > nums[ma]) ma = i;
}
int lo = Math.min(mi, ma), hi = Math.max(mi, ma);
return Math.min(hi + 1, Math.min(n - lo, lo + 1 + (n - hi)));
}C++
int minimumDeletions(vector<int>& nums) {
int n = (int) nums.size(), mi = 0, ma = 0;
for (int i = 1; i < n; i++) {
if (nums[i] < nums[mi]) mi = i;
if (nums[i] > nums[ma]) ma = i;
}
int lo = min(mi, ma), hi = max(mi, ma);
return min(hi + 1, min(n - lo, lo + 1 + (n - hi)));
}JavaScript
var minimumDeletions = function(nums) {
var n = nums.length, mi = 0, ma = 0;
for (var i = 1; i < n; i++) {
if (nums[i] < nums[mi]) mi = i;
if (nums[i] > nums[ma]) ma = i;
}
var lo = Math.min(mi, ma), hi = Math.max(mi, ma);
return Math.min(hi + 1, Math.min(n - lo, lo + 1 + (n - hi)));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms