2091. Removing Minimum and Maximum From Array

MediumGreedyArray
Leetcode Link

Problem Description

In this problem, we are given an array nums which contains distinct integers. It is 0-indexed, which means the indexing of elements in the array starts with 0. Among all the elements in the nums array, there is one element with the lowest value, termed as the minimum, and one with the highest value, known as the maximum. Our objective is to remove these two elements from the array.

A deletion involves removing an element either from the front (beginning) of the array or from the back (end) of the array. The task is to determine the minimum number of such deletions required to remove both the minimum and maximum elements from the array.

To succeed, we need to find a strategy that minimizes the total number of deletions by intelligently deciding whether to start from the front or the back of the array, as well as considering the possibility of removing elements from both ends.

Intuition

When approaching the solution, we focus on the positions (indexes) of the minimum and maximum elements in the array. The main idea hinges upon the realization that the number of deletions needed is influenced by the relative locations of these two elements.

Firstly, we identify the indexes of both the minimum and maximum elements by scanning through the array.

Then, our strategy involves considering three scenarios:

  • Remove elements from the front until both the minimum and maximum elements are deleted.
  • Remove elements from the back until both elements are deleted.
  • Remove some elements from the front to delete one of the elements and some from the back to delete the other one.

To achieve the minimum number of deletions, we calculate the number of deletions needed for each of the scenarios and return the smallest one.

The insight here is to use the indexes of minimum and maximum elements efficiently to minimize the number of operations, as direct removals would be inefficient for large arrays.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which technique can we use to find the middle of a linked list?

Solution Approach

The solution approach for this problem leverages a straightforward scan of the array to determine the positions (indexes) of the minimum and maximum elements.

The following steps are taken in the implementation:

  1. Initialize two variables, mi and mx, to store the indexes of the minimum and maximum elements, respectively. We start by assuming the first element (at index 0) is both the minimum and maximum, hence mi = mx = 0.

  2. Loop through every element num in the nums list, keeping track of the current index i. During each iteration:

    • If the current element is less than nums[mi], update mi with the current index i because a new minimum has been found.
    • Similarly, if the current element is greater than nums[mx], update mx with the current index i as a new maximum has been found.

  3. After identifying the indexes of the minimum and maximum elements, ensure that mi is less than or equal to mx by swapping them if that is not the case. This simplifies the calculation that follows, because we will be dealing with three scenarios represented by contiguous sections of the array to be deleted.

  4. Calculate the total number of deletions required for each of the three above-mentioned deletion strategies:

    • Strategy 1: Remove elements from the beginning (front) up to and including the maximum index (mx). The number of deletions would be mx + 1, since array indexing starts at 0.
    • Strategy 2: Remove elements from the end (back) up to and including the minimum index (mi). The number of deletions here would be len(nums) - mi.
    • Strategy 3: Remove elements from the front up to and including the minimum index (mi + 1) and from the back to the maximum index (len(nums) - mx), combining these two gives mi + 1 + len(nums) - mx.

  5. Return the minimum value out of the three calculated strategies to achieve the minimum number of deletions needed to remove both the minimum and maximum elements from the array. This is done using the built-in min() function with the above mentioned three results as arguments.

The Python code is elegant and concise due to its use of list enumeration for index tracking, conditional statements for dynamic updates, and the min() function for direct comparison.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's illustrate the solution approach with a small example:

Assume we have the array nums = [3, 2, 5, 1, 4].

  1. We initialize mi = mx = 0. Currently, nums[mi] = nums[mx] = 3.

  2. We start looping through the elements:

    • num = 2, i = 1: 2 is not less than 3, so mi remains unchanged. 2 is not greater than 3, so mx also remains unchanged.
    • num = 5, i = 2: 5 is greater than 3, so we update mx to 2. 5 is not less than 3, so mi remains unchanged.
    • num = 1, i = 3: 1 is less than 3, so we update mi to 3. 1 is not greater than 5, so mx remains 2.
    • num = 4, i = 4: 4 is not less than 1, and it's not greater than 5, so both mi and mx remain unchanged.

After the loop, mi = 3 (minimum element 1 at index 3) and mx = 2 (maximum element 5 at index 2).

  1. Since mi is not less than mx, we do not swap them.

  2. Calculate the number of deletions for each strategy:

    • Strategy 1: Removing from the front to the maximum index mx is mx + 1, which equals 3 deletions.
    • Strategy 2: Removing from the back to the minimum index mi is len(nums) - mi, which is 5 - 3, resulting in 2 deletions.
    • Strategy 3: Removing from the front up to mi and from the back beyond mx is mi + 1 + len(nums) - mx, which is 3 + 1 + 5 - 2, totaling 7 deletions.

  3. Finally, return the minimum value out of the calculated strategies: min(3, 2, 7) which equals 2.

Therefore, the minimum number of deletions required to remove both the minimum and maximum elements from the array [3, 2, 5, 1, 4] is 2. This occurs by removing the last two elements (strategy 2).

Solution Implementation

1class Solution:
2    def minimumDeletions(self, nums: List[int]) -> int:
3        # Initialize indices for the minimum and maximum value elements
4        min_index = max_index = 0
5      
6        # Iterate over the list to find indices of the minimum and maximum elements
7        for i, num in enumerate(nums):
8            if num < nums[min_index]:  # A new minimum element found
9                min_index = i
10            if num > nums[max_index]:  # A new maximum element found
11                max_index = i
12      
13        # Ensure that min_index is always less than or equal to max_index
14        if min_index > max_index:
15            min_index, max_index = max_index, min_index
16      
17        # Calculate the minimum number of deletions using three strategies:
18        # 1. Delete from the front to the max element
19        # 2. Delete from the min element to the end of the list
20        # 3. Delete from both ends to the min and max elements
21        # Then return the strategy that results in the fewest deletions
22        return min(
23            max_index + 1,  # Deleting from the front to the max element
24            len(nums) - min_index,  # Deleting from the min element to the end
25            min_index + 1 + len(nums) - max_index  # Deleting from both ends
26        )
27
1class Solution {
2    public int minimumDeletions(int[] nums) {
3        // Initialize the variables to store the index of minimum and maximum element in array
4        int minIndex = 0;
5        int maxIndex = 0;
6        // Length of the array
7        int n = nums.length;
8      
9        // Iterate through the array to find the indices of the minimum and maximum elements
10        for (int i = 0; i < n; ++i) {
11            // Update the index of the minimum element if a smaller element is found
12            if (nums[i] < nums[minIndex]) {
13                minIndex = i;
14            }
15            // Update the index of the maximum element if a larger element is found
16            if (nums[i] > nums[maxIndex]) {
17                maxIndex = i;
18            }
19        }
20      
21        // Make sure the minIndex is always less than maxIndex for ease of calculation
22        if (minIndex > maxIndex) {
23            // Swap minIndex with maxIndex
24            int temp = maxIndex;
25            maxIndex = minIndex;
26            minIndex = temp;
27        }
28      
29        // Calculate the minimum deletions needed, considering three different scenarios:
30        // 1. Removing elements from the beginning up to the maxIndex
31        // 2. Removing elements from the minIndex to the end
32        // 3. Removing elements from both ends surrounding the min and max
33        // Return the smallest of these three options
34        return Math.min(Math.min(maxIndex + 1, n - minIndex),
35                        minIndex + 1 + n - maxIndex);
36    }
37}
38
1class Solution {
2public:
3    int minimumDeletions(vector<int>& nums) {
4        int minIndex = 0; // Index of the smallest number
5        int maxIndex = 0; // Index of the largest number
6        int n = nums.size(); // The total number of elements in nums
7      
8        // Loop to find indices of the smallest and largest numbers
9        for (int i = 0; i < n; ++i) {
10            if (nums[i] < nums[minIndex]) { // Check for new minimum
11                minIndex = i;
12            }
13            if (nums[i] > nums[maxIndex]) { // Check for new maximum
14                maxIndex = i;
15            }
16        }
17      
18        // Ensure minIndex is smaller than maxIndex for easier calculation
19        if (minIndex > maxIndex) {
20            int temp = minIndex;
21            minIndex = maxIndex;
22            maxIndex = temp;
23        }
24      
25        // Three possible ways to remove the min and max, take the minimum deletions needed
26        return min(
27            min(
28                maxIndex + 1, // Delete all from start to maxIndex, inclusive
29                n - minIndex // Delete all from minIndex to end
30            ), 
31            minIndex + 1 + n - maxIndex // Delete from start to minIndex and from maxIndex to end
32        );
33    }
34};
35
1function minimumDeletions(nums: number[]): number {
2    // Find the number of elements in the array
3    const numElements = nums.length;
4  
5    // If the array contains only one element, one deletion is required
6    if (numElements === 1) return 1;
7  
8    // Find the indices of the minimum and maximum elements in the array
9    let minIndex = nums.indexOf(Math.min(...nums));
10    let maxIndex = nums.indexOf(Math.max(...nums));
11  
12    // Calculate the leftmost and rightmost positions among the min and max indices
13    let leftIndex = Math.min(minIndex, maxIndex);
14    let rightIndex = Math.max(minIndex, maxIndex);
15  
16    // Calculate the possible numbers of deletions
17    // if removing from the left towards the right
18    let deleteLeftRight = leftIndex + 1 + numElements - rightIndex;
19    // if removing from the left only
20    let deleteLeftOnly = rightIndex + 1;
21    // if removing from the right only
22    let deleteRightOnly = numElements - leftIndex;
23  
24    // Return the minimum number of deletions amongst the calculated options
25    return Math.min(deleteLeftRight, deleteLeftOnly, deleteRightOnly);
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input list nums. This is because the code consists of a single loop that traverses the entire list to find the minimum and maximum elements' indices, which takes linear time in the size of the input.

The space complexity of the code is O(1). The extra space used by the code includes only a fixed number of integer variables mi (minimum index) and mx (maximum index), which do not depend on the input size, therefore the space used is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫