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

Sujal Modanwal
Last Updated: May 13, 2022

Introduction

An array is a collection of variables of the same data type like integers, floating-point numbers, characters, or the derived data types like structure, pointers, etc. In any interview or coding test, this is very likely that you will face at least one question based on arrays. In this blog, we will see one such problem which will build our understanding to solve similar array problems. The problem is to remove minimum and maximum from an array by minimizing deletion from either end.

Deletion of elements from either end can be explained as removing elements from any of the two ends without disturbing other elements of the array.

Problem Statement

An array of integers of size ‘N’ is given. You have to find the minimum number of elements to be deleted from either end to remove the minimum and maximum elements of the array.

Example

Input: nums = [4]

Output: 1

Explanation: 4 is the minimum element as well as the maximum element of the array. So only one deletion will remove both minimum and maximum elements from the array. 


Input: nums = [4, 7, 5, 3, 2, 1]

Output: 3

Explanation: 1 and 7 are the minimum and maximum elements of the array, respectively. So,  to remove them:

  • We need to remove 1 from the right end of the array
    • The array will be [4, 7, 5, 3, 2]
  • Then we need to remove 4 from the left end
    • The array will be [7, 5, 3, 2]
  • And finally, we need to remove 7 again from the left end of the array
    • The array will be [5, 3, 2]

So both minimum and maximum elements are removed from the array in 3 deletions.

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;
}

Input

5
2 1 3 5 4

Output

Minimum deletions for removal of min and max are: 4

Complexity Analysis

Time Complexity

O(2N), 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 = 2N

Auxiliary Space

O(1).

As no extra space is required.

We can do better than O(2N) 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;
}

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.

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 CodeStudio 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!

 

Was this article helpful ?
0 upvotes