Removing Minimum and Maximum From Array

Medium
844.

Removing Minimum and Maximum From Array

Removing Minimum and Maximum From Array is a medium coding problem on arrays and greedy, asked in Amazon, Microsoft and Zoho interviews.

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] <= 100000
  • All values in nums are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDeletions = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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] <= 100000
  • All values in nums are distinct.

Hints for Removing Minimum and Maximum From Array

  1. Hint 1

    Only the two positions matter: where the minimum sits and where the maximum sits.

  2. Hint 2

    There are exactly three strategies — both from the front, both from the back, or one from each end.

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

  1. Locate the index of the minimum and of the maximum; let lo and hi be the smaller and larger of the two.
  2. Both from the front costs hi + 1; both from the back costs n - lo; one from each end costs (lo + 1) + (n - hi).
  3. 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