Minimize Deletions from Either End to Remove Minimum and Maximum from Array

Brute Force Algorithm

The above problem can be solved with a brute force algorithm explained as below:

• First, we need to find the position of minimum and maximum integers in the array. Let the positions of minimum and maximum elements be ‘IDX1’ and ‘IDX2’, respectively
• We will also need a variable ‘minDel’ to store the minimum number of deletions
• Then we will create a function checkRemoveMinMax(vector<int> nums, int left, int right), where we will first check if the range [left, right] doesn’t include any of both ‘IDX1’ and ‘IDX2’, we will simply update ‘minDel’ with the number of deletions already done
• If any of the ‘IDX1’ or ‘IDX2’ is included in the range [left, right], we will proceed with the function. We only have two options, whether to remove the element from the front or from the end of the array. So we will recursively call the same function but with changed arguments,  
  • Removing the first element: checkRemoveMinMax(nums, left + 1, right) 
  • Removing the second element: checkRemoveMinMax(nums, left, right - 1)
• In this way, we will check all the possible ways to reach the required outcome and return the minimum number of deletions among them

Program

// Program to find minimum removal of min and max elements.
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Variables to store minimum and maximum element's indices.
int IDX1, IDX2;
 
// Variable to store total elements in the array.
int N;
 
// Variable to store minimum deletions.
int minDel;
 
// Function to find minimum deletions.
void checkRemoveMinMax(vector<int>& nums, int left, int right)
{
      // Taking minimum and maximum separately.
      int L = min(IDX1, IDX2);
      int R = max(IDX1, IDX2);
 
      // Checking if the minimum and maximum index are covered between left and right.
      if ((L < left && R > right) || (L < left && R < left) || (L > right && R > right))
      {
            minDel = min(minDel, left + N - 1 - right);
            return;
      }
 
      checkRemoveMinMax(nums, left + 1, right);
      checkRemoveMinMax(nums, left, right - 1);
}
 
// Main function.
int main()
{
      // Input of number of elements.
      cin >> N;
      minDel = N;
 
      // Vector to store the elements.
      vector<int> nums(N);
      for (int i = 0; i < N; i++)
            cin >> nums[i];
 
      // Storing indices of minimum and maximum elements.
      IDX1 = min_element(nums.begin(), nums.end()) - nums.begin();
      IDX2 = max_element(nums.begin(), nums.end()) - nums.begin();
 
      // Calling the responsible function.
      checkRemoveMinMax(nums, 0, N - 1);
 
      // Printing the output.
      cout << "Minimum deletions for removal of min and max are: " << minDel;
}

You can also try this code with Online C++ Compiler

Run Code

Input

5
2 1 3 5 4

Output

Minimum deletions for removal of min and max are: 4

Complexity Analysis

Time Complexity

O(2^N), where ‘N’ is the size of the given array.

Explanation: At every index, there will be 2 calls to the function checkRemoveMinMax(), resulting

2 x 2 x 2 … N times = 2^N

Auxiliary Space

O(1).

As no extra space is required.

We can do better than O(2^N) with the below approach. 

Optimized Approach

Intuition

We are asked to remove the minimum and maximum elements in minimum deletions from the array, so their position from the left end and right end are points of interest. 

Approach

First, we need to find the position of minimum and maximum integers in the array. Let the positions of minimum and maximum elements be ‘IDX1’ and ‘IDX2’ respectively.

Let ‘L’ be the minimum among ‘IDX1’, and ‘IDX2’ and ‘R’ be the maximum among ‘IDX1’ and ‘IDX2’.

[ _ _ _ _ _ IDX1/IDX2 _ _ _ _ _ _ IDX1/IDX2 _ _ _ _ _ _ ]

<----- t —-->  (L)   <----- u —--->   (R)  <---- v ----->

<----------------------------N---------------------------->

Let 

• t be the distance of “L’ from the left end
• u be the distance between ‘L’ and ‘R’ 
• v be the distance of ‘R’ from the right end
   

So to reach the index ‘L’ and ‘R’, while doing deletions can be done in three ways.

1. We can do the deletions from the left end only. So the number of deletions will be

left= t + u = R + L

1. We can do deletions from the right end only. So the number of deletions will

right = v + u = N - L

1. We can do deletions from the left and right end both. So the number of deletions will be

both = t + v = L + 1 + N - R
 

So above are the three ways with which deletions can be done to remove the minimum and maximum numbers from the array. Our answer will be the minimum of all three.

Program

// Program to find minimum removal of min and max elements.
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Function to find minimum deletions.
int minimumDel(vector<int>& nums)
{
      // Storing the size of nums.
      int N = nums.size();
 
      // Storing indices of minimum and maximum element.
      int idx1 = min_element(nums.begin(), nums.end()) - nums.begin();
      int idx2 = max_element(nums.begin(), nums.end()) - nums.begin();
 
      // Taking minimum and maximum separately.
      int L = min(idx1, idx2);
      int R = max(idx1, idx2);
 
      // Deletion from left end only.
      int left = R + L;
 
      // Deletion from right end only.
      int right = N - L;
 
      // Deletion from both ends.
      int both = L + 1 + N - R;
 
      // Taking minimum of all three
      int ans = min({left, right, both});
 
      // Returning the final answer.
      return ans;
}
 
// Main function.
int main()
{
      // Variable to store total elements in the array.
      int N;
      cin >> N;
 
      // Vector to store the elements.
      vector<int> nums(N);
      for (int i = 0; i < N; i++)
            cin >> nums[i];
 
      int ans = minimumDel(nums);
      cout << "Minimum deletions for removal of min and max are: " << ans;
}

You can also try this code with Online C++ Compiler

Run Code

Input

5
2 3 1 5 4

Output

Minimum deletions for removal of min and max are: 3

Complexity Analysis

Time Complexity

O(N), where ‘N’ is the size of the given array.

Explanation: 

• O(N) to find the minimum and maximum element from the array.
• All other operations require constant time.

Auxiliary Space

O(1), as no extra space, is required.

Check out this problem - First And Last Occurrences Of X

Key Takeaways

Minimize deletions from either end to remove minimum and maximum from the array is an interesting question, but it is not the only interesting question here. Find more interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!