Removing Minimum and Maximum From Array — LeetCode 2091 Python Solution

The problem

You are given a 0-indexed array of distinct integers nums. There is an element in nums that has the lowest value and an element that has the highest value.

Example

Input

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

Output

5

Explanation

The minimum element in the array is nums[5], which is 1.

Python solution

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        mi = mx = 0
        for i, num in enumerate(nums):
            if num < nums[mi]:
                mi = i
            if num > nums[mx]:
                mx = i
        if mi > mx:
            mi, mx = mx, mi
        return min(mx + 1, len(nums) - mi, mi + 1 + len(nums) - mx)

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2091. Removing Minimum and Maximum From Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems