Given an array arr[] consisting of only 0 and 1. The task is to find the minimum number of deletions from the front and back of the array, such that the new modified array consists of an equal number of 0’s and 1’s.
Examples:
Input: arr[] = {1, 1, 0, 1}
Output: 2
Explanation: Two ones from the starting or first and last element can be removedInput: arr[] = {0, 1, 1, 1, 0}
Output: 3
Explanation: First three elements can be removed or last three elements
Approach: The problem can be solved using greedy approach. As each element of the array can be either 0 or 1, so consider 0 as -1 and 1 as 1 itself. Then find the largest subarray that consists of an equal number of 1s and 0s. Then subtract the size of this subarray from the total size of the array. This approach works because at any moment the approach tries to keep the size of the subarray as large as possible so that only a minimum number of elements from the ends can be removed. See the following diagram for a better understanding.
As it can be seen from the diagram, as the size of middle part y increases which consists of an equal number of 0s and 1s, automatically the size of part (x + z) decreases.
Below is the implementation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// the minimum number of deletionsint solve(vector<int> arr){ // Size of the array int sz = arr.size(); // Store running sum of array int summe = 0; // To store index of the sum unordered_map<int, int> index; // Initially sum is 0 with index -1 index[summe] = -1; // Store length of largest subarray int ans = 0, curr_len = 0; for (int i = 0; i < sz; i++) { // If curr_element is 0, add -1 if (arr[i] == 0) summe -= 1; // If curr_element is 1, add 1 else summe += 1; // Check if sum already occurred if (index.find(summe) != index.end()) { // Calculate curr subarray length curr_len = i - index[summe]; // Store the maximum value // in the ans ans = max(ans, curr_len); } // Sum occurring for the first time // So store this sum with current index else index[summe] = i; } // Return diff between size // and largest subarray return (sz - ans);}// Driver codeint main(){ vector<int> arr = { 1, 1, 0, 1 }; int val = solve(arr); cout << val;}// This code is contributed by Samim Hossain Mondal. |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to calculate // the minimum number of deletions static int solve(int[] arr) { // Size of the array int sz = arr.length; // Store running sum of array int summe = 0; // To store index of the sum HashMap<Integer,Integer> index = new HashMap<Integer,Integer>(); // Initially sum is 0 with index -1 index.put(summe, -1); // Store length of largest subarray int ans = 0, curr_len = 0; for (int i = 0; i < sz; i++) { // If curr_element is 0, add -1 if (arr[i] == 0) summe -= 1; // If curr_element is 1, add 1 else summe += 1; // Check if sum already occurred if (index.containsKey(summe) ) { // Calculate curr subarray length curr_len = i - index.get(summe); // Store the maximum value // in the ans ans = Math.max(ans, curr_len); } // Sum occurring for the first time // So store this sum with current index else index.put(summe, i); } // Return diff between size // and largest subarray return (sz - ans); } // Driver code public static void main(String[] args) { int []arr = { 1, 1, 0, 1 }; int val = solve(arr); System.out.print(val); }}// This code is contributed by 29AjayKumar |
Python3
# Python code to implement the given approachfrom collections import defaultdictclass Solution: # Function to calculate # the minimum number of deletions def solve(self, arr): # Size of the array size = len(arr) # Store running sum of array summe = 0 # To store index of the sum index = defaultdict(int) # Initially sum is 0 with index -1 index[summe] = -1 # Store length of largest subarray ans = 0 for i in range(size): # If curr_element is 0, add -1 if (arr[i] == 0): summe -= 1 # If curr_element is 1, add 1 else: summe += 1 # Check if sum already occurred if (summe in index): # Calculate curr subarray length curr_len = i - index[summe] # Store the maximum value # in the ans ans = max(ans, curr_len) # Sum occurring for the first time # So store this sum with current index else: index[summe] = i # Return diff between size # and largest subarray return (size - ans)if __name__ == "__main__": arr = [1, 1, 0, 1] obj = Solution() val = obj.solve(arr) print(val) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to calculate // the minimum number of deletions static int solve(int[] arr) { // Size of the array int sz = arr.Length; // Store running sum of array int summe = 0; // To store index of the sum Dictionary<int,int> index = new Dictionary<int, int>(); // Initially sum is 0 with index -1 index.Add(summe, -1); // Store length of largest subarray int ans = 0, curr_len = 0; for (int i = 0; i < sz; i++) { // If curr_element is 0, add -1 if (arr[i] == 0) summe -= 1; // If curr_element is 1, add 1 else summe += 1; // Check if sum already occurred if (index.ContainsKey(summe) ) { // Calculate curr subarray length curr_len = i - index[summe]; // Store the maximum value // in the ans ans = Math.Max(ans, curr_len); } // Sum occurring for the first time // So store this sum with current index else index[summe] = i; } // Return diff between size // and largest subarray return (sz - ans); } // Driver code public static void Main() { int []arr = { 1, 1, 0, 1 }; int val = solve(arr); Console.Write(val); }}// This code is contributed by gfgking |
Javascript
<script> // JavaScript code for the above approach // Function to calculate // the minimum number of deletions function solve(arr) { // Size of the array size = arr.length // Store running sum of array let summe = 0 // To store index of the sum index = new Map(); // Initially sum is 0 with index -1 index.set(summe, -1); // Store length of largest subarray ans = 0 for (let i = 0; i < size; i++) { // If curr_element is 0, add -1 if (arr[i] == 0) summe -= 1 // If curr_element is 1, add 1 else summe += 1 // Check if sum already occurred if (index.has(summe)) { // Calculate curr subarray length curr_len = i - index.get(summe) // Store the maximum value // in the ans ans = Math.max(ans, curr_len) } // Sum occurring for the first time // So store this sum with current index else index.set(summe, i) } // Return diff between size // and largest subarray return (size - ans) } // Driver code arr = [1, 1, 0, 1] val = solve(arr) document.write(val) // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments