Get started

Removing Minimum and Maximum From Array — Medium Problem & Solution

nums holds distinct integers. One deletion removes the element at the front or the back of the array.

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

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))

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue