2091. Removing Minimum and Maximum From Array

2091. Removing Minimum and Maximum From Array

Medium

---

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. We call them the minimum and maximum respectively. Your goal is to remove both these elements from the array.

A deletion is defined as either removing an element from the front of the array or removing an element from the back of the array.

Return the minimum number of deletions it would take to remove both the minimum and maximum element from the array.

 

Example 1:

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.
The maximum element in the array is nums[1], which is 10.
We can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.
This results in 2 + 3 = 5 deletions, which is the minimum number possible.

 

Example 2:

Input: nums = [101]
Output: 1
Explanation:  
There is only one element in the array, which makes it both the minimum and maximum element.
We can remove it with 1 deletion.

 

 

주어진 배열에서 가장 큰 숫자와 가장 작은 숫자를 제거할 때

몇 번 만에 제거할 수 있는지 알아내는 문제입니다.

 

이때 제거하는 방법은 3가지입니다.

case 1. 배열의 앞에서부터 제거한다.

case 2. 배열의 뒤에서부터 제거한다.

case 3. 배열의 앞과 뒤에서 부터 제거한다.

 

의사코드

1. nums의 길이가 1이면 1을 리턴한다. 

2.  nums에서 가장 큰 수, 가장 작은 수의 인덱스 번호를 찾는다.

3. 각 case 별로 제거 횟수를 구하고 그중 가장 작은 횟수의 값을 리턴한다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDeletions = function(nums) {
    if(nums.length===1) return 1
    
    const [minIdx, maxIdx] = findMinIdxAndMaxId(nums)
    
    const len = nums.length
    const left = Math.min(minIdx, maxIdx)
    const right = Math.max(minIdx, maxIdx)
    
    // case 1 : 앞에서 부터 삭제 right + 1
    // case 2 : 뒤에서 부터 삭제 len - left
    // case 3 : 앞 뒤에서 부터 삭제  (left + 1) + (len - right)
    return Math.min(right + 1, len - left, left + 1 + len - right)
};

function findMinIdxAndMaxId(nums) {
    let minIdx = 0, maxIdx = 0 
    
    for(let i=0; i<nums.length;i++){
        if(nums[i] < nums[minIdx]) minIdx = i
        if(nums[i] > nums[maxIdx]) maxIdx = i
    }
    
    return [minIdx, maxIdx]
}