Given array of integers arr[] of size N, the task is to find the count of minimum number of deletion operations to remove minimum and the maximum element from the array. The elements can only be deleted from either end of the array.
Examples:
Input: arr = [2, 10, 7, 5, 4, 1, 8, 6]
Output: 5
Explanation: The minimum element is 1 and the maximum element is 10. We can visualise the deletion operations as below:
[2, 10, 7, 5, 4, 1, 8, 6]
[2, 10, 7, 5, 4, 1, 8]
[2, 10, 7, 5, 4, 1]
[2, 10, 7, 5, 4]
[10, 7, 5, 4]
[7, 5, 4]Total 5 deletion operations performed. There is no other sequence with less deletions in which the minimum and maximum can be deleted.
Input: arr = [56]
Output: 1
Explanation: Because the array only has one entry, it serves as both the lowest and maximum value. With a single delete, we can eliminate it.Input: arr = [2, 5, 8, 3, 6, 4]
Output: 3
Explanation: The minimum element is 2 and the maximum element is 8. We can visualise the deletion operations as below:
[2, 5, 8, 3, 6, 4]
[5, 8, 3, 6, 4]
[8, 3, 6, 4]
[3, 6, 4]Total 3 deletions are performed. It is the minimum possible number of deletions.
Approach: The above problem can be solved using below observation:
Suppose the max and min elements exists at index i and j, or vice versa, as shown below:
[ _ _ _ _ _ min/max _ _ _ _ _ _ max/min _ _ _ _ _ _ ] <-- a --> (i) <--- b ---> (j) <---- c ----> <-----------------------N ------------------------->
where,
- i, j: index of either max or min element of the array
- a: distance of the minimum (or maximum) element from starting
- b: distance between minimum and maximum element
- c: distance between maximum( or minimum) element from ending
- N: length of array
Now let’s look at different possible ways of deletion:
- For removing one from start and the other from end:
No. of deletion = (a + c) = ( (i + 1) + (n – j) )
- For removing both of them from starting of the array:
No. of deletion = (a + b) = (j + 1)
- For removing both of them from the end of the array:
No. of deletion = (b + c) = (n – i)
Using the above equations we can now easily get distances using the index of min and max element. The answer is minimum of these 3 cases
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to return// the minimum number of deletionsint minDeletions(vector<int>& nums){ int n = nums.size(); // Index of minimum element int minindex = min_element(nums.begin(), nums.end()) - nums.begin(); // Index of maximum element int maxindex = max_element(nums.begin(), nums.end()) - nums.begin(); // Assume that minimum element // always occur before maximum element. // If not, then swap its index. if (minindex > maxindex) swap(minindex, maxindex); // Deletion operations for case-1 int bothend = (minindex + 1) + (n - maxindex); // Deletion operations for case-2 int frontend = (maxindex + 1); // Deletion operations for case-3 int backend = (n - minindex); // Least number of deletions is the answer int ans = min(bothend, min(frontend, backend)); return ans;}// Driver codeint main(){ vector<int> arr{ 2, 10, 7, 5, 4, 1, 8, 6 }; cout << minDeletions(arr) << endl; vector<int> arr2{ 56 }; cout << minDeletions(arr2); return 0;} |
Java
// Java code to implement the above approachimport java.util.Arrays;import java.util.stream.IntStream;class GFG{// Function to return the // minimum number of deletionsint minDeletions(int[] nums){ int n = nums.length; // Index of minimum element int minindex = findIndex(nums, Arrays.stream(nums).min().getAsInt()); // Index of maximum element int maxindex = findIndex( nums, Arrays.stream(nums).max().getAsInt()); // Assume that minimum element // always occur before maximum element. // If not, then swap its index. if (minindex > maxindex) { minindex = minindex + maxindex; maxindex = minindex - maxindex; minindex = minindex - maxindex; } // Deletion operations for case-1 int bothend = (minindex + 1) + (n - maxindex); // Deletion operations for case-2 int frontend = (maxindex + 1); // Deletion operations for case-3 int backend = (n - minindex); // Least number of deletions is the answer int ans = Math.min( bothend, Math.min(frontend, backend)); return ans;}// Function to find the index of an elementpublic static int findIndex(int arr[], int t){ int len = arr.length; return IntStream.range(0, len) .filter(i -> t == arr[i]) .findFirst() // first occurrence .orElse(-1); // No element found}// Driver codepublic static void main(String[] args){ int[] arr = { 2, 10, 7, 5, 4, 1, 8, 6 }; System.out.print(new GFG().minDeletions(arr) + "\n"); int []arr2 = { 56 }; System.out.print(new GFG().minDeletions(arr2));}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 code to implement the above approach# Function to return# the minimum number of deletionsdef minDeletions(nums): n = len(nums) # Index of minimum element minindex = nums.index(min(nums)) # Index of maximum element maxindex = nums.index(max(nums)) # Assume that minimum element # always occur before maximum element. # If not, then swap its index. if (minindex > maxindex): minindex, maxindex = maxindex, minindex # Deletion operations for case-1 bothend = (minindex + 1) + (n - maxindex) # Deletion operations for case-2 frontend = (maxindex + 1) # Deletion operations for case-3 backend = (n - minindex) # Least number of deletions is the answer ans = min(bothend, min(frontend, backend)) return ans# Driver codeif __name__ == "__main__": arr = [2, 10, 7, 5, 4, 1, 8, 6] print(minDeletions(arr)) arr2 = [56] print(minDeletions(arr2)) # This code is contributed by ukasp. |
C#
// C# code to implement the above approachusing System;using System.Linq;public class GFG{// Function to return the // minimum number of deletionsint minDeletions(int[] nums){ int n = nums.Length; // Index of minimum element int minindex = findIndex(nums, nums.Min()); // Index of maximum element int maxindex = findIndex( nums, nums.Max()); // Assume that minimum element // always occur before maximum element. // If not, then swap its index. if (minindex > maxindex) { minindex = minindex + maxindex; maxindex = minindex - maxindex; minindex = minindex - maxindex; } // Deletion operations for case-1 int bothend = (minindex + 1) + (n - maxindex); // Deletion operations for case-2 int frontend = (maxindex + 1); // Deletion operations for case-3 int backend = (n - minindex); // Least number of deletions is the answer int ans = Math.Min( bothend, Math.Min(frontend, backend)); return ans;}// Function to find the index of an elementpublic static int findIndex(int []arr, int t){ int len = arr.Length; return Array.IndexOf(arr, t);}// Driver codepublic static void Main(String[] args){ int[] arr = { 2, 10, 7, 5, 4, 1, 8, 6 }; Console.Write(new GFG().minDeletions(arr) + "\n"); int []arr2 = { 56 }; Console.Write(new GFG().minDeletions(arr2));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code to implement the above approach // Function to return // the minimum number of deletions const minDeletions = (nums) => { let n = nums.length; // Index of minimum element let minindex = nums.indexOf(Math.min(...nums)); // Index of maximum element let maxindex = nums.indexOf(Math.max(...nums)); // Assume that minimum element // always occur before maximum element. // If not, then swap its index. if (minindex > maxindex) { let temp = minindex; minindex = maxindex; maxindex = temp; } // Deletion operations for case-1 let bothend = (minindex + 1) + (n - maxindex); // Deletion operations for case-2 let frontend = (maxindex + 1); // Deletion operations for case-3 let backend = (n - minindex); // Least number of deletions is the answer let ans = Math.min(bothend, Math.min(frontend, backend)); return ans; } // Driver code let arr = [2, 10, 7, 5, 4, 1, 8, 6]; document.write(`${minDeletions(arr)}<br/>`); let arr2 = [56]; document.write(minDeletions(arr2)); // This code is contributed by rakeshsahni</script> |
Output
5 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
