Given binary array. The task is to find the length of subarray with minimum number of 1s.
Note: It is guaranteed that there is atleast one 1 present in the array.
Examples :
Input : arr[] = {1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1}
Output : 3
Minimum length subarray of 1s is {1, 1}.
Input : arr[] = {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}
Output : 1
Simple Solution: A simple solution is to consider every subarray and count 1’s in every subarray. Finally return return size of minimum length subarray of 1s.
C++
#include <bits/stdc++.h>using namespace std;int subarrayWithMinOnes(int arr[], int n){ int ans = INT_MAX; // consider all subarrays starting from index i for (int i = 0; i < n; i++) { // consider all subarrays ending at index j for (int j = i+1; j < n; j++) { int count = 0; bool flag = true; // count the number of 1s in the current subarray for (int k = i; k <= j; k++) { if (arr[k] != 1) { flag = false; break; } else count++; } // if current subarray has all 1s, update ans if (flag) ans = min(ans, count); } } return ans;}int main(){ int arr[] = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << subarrayWithMinOnes(arr, n) << endl; return 0;}//This code is conntributed by Naveen Gujjar |
Java
import java.util.*;public class Main { public static int subarrayWithMinOnes(int[] arr, int n) { int ans = Integer.MAX_VALUE; // consider all subarrays starting from index i for (int i = 0; i < n; i++) { // consider all subarrays ending at index j for (int j = i+1; j < n; j++) { int count = 0; boolean flag = true; // count the number of 1s in the current subarray for (int k = i; k <= j; k++) { if (arr[k] != 1) { flag = false; break; } else count++; } // if current subarray has all 1s, update ans if (flag) ans = Math.min(ans, count); } } return ans; } public static void main(String[] args) { int[] arr = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 }; int n = arr.length; System.out.println(subarrayWithMinOnes(arr, n)); }} |
Python3
def subarrayWithMinOnes(arr, n): ans = float('inf') # consider all subarrays starting from index i for i in range(n): # consider all subarrays ending at index j for j in range(i+1, n): count = 0 flag = True # count the number of 1s in the current subarray for k in range(i, j+1): if arr[k] != 1: flag = False break else: count += 1 # if current subarray has all 1s, update ans if flag: ans = min(ans, count) return ansarr = [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1]n = len(arr)print(subarrayWithMinOnes(arr, n)) |
Javascript
function subarrayWithMinOnes(arr, n) { let ans = Infinity; for (let i = 0; i < n; i++) { for (let j = i+1; j < n; j++) { let count = 0; let flag = true; for (let k = i; k <= j; k++) { if (arr[k] !== 1) { flag = false; break; } else { count++; } } if (flag) { ans = Math.min(ans, count); } } } return ans;}let arr = [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1];let n = arr.length;console.log(subarrayWithMinOnes(arr, n)); |
C#
using System;class Program { static int SubarrayWithMinOnes(int[] arr, int n) { int ans = int.MaxValue; // consider all subarrays starting from index i for (int i = 0; i < n; i++) { // consider all subarrays ending at index j for (int j = i + 1; j < n; j++) { int count = 0; bool flag = true; // count the number of 1s in the current // subarray for (int k = i; k <= j; k++) { if (arr[k] != 1) { flag = false; break; } else count++; } // if current subarray has all 1s, update // ans if (flag) ans = Math.Min(ans, count); } } return ans; } static void Main(string[] args) { int[] arr = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 }; int n = arr.Length; Console.WriteLine(SubarrayWithMinOnes(arr, n)); }}// This code is contributed by sarojmcy2e |
Output
2
Time complexity: O(n^3)
Auxiliary Space: O(1)
Efficient Solution: An efficient solution is traverse array from left to right. If we see a 1, we increment count. If we see a 0, and count of 1s so far is positive, calculate minimum of count and result and reset count to zero.
Below is the implementation of the above approach:
C++
// C++ program to count minimum length// subarray of 1's in a binary array.#include <bits/stdc++.h>using namespace std;// Function to count minimum length subarray// of 1's in binary array arr[0..n-1]int getMinLength(bool arr[], int n){ int count = 0; // initialize count int result = INT_MAX; // initialize result for (int i = 0; i < n; i++) { if (arr[i] == 1) { count++; } else { if (count != 0) result = min(result, count); count = 0; } } return result;}// Driver codeint main(){ bool arr[] = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << getMinLength(arr, n) << endl; return 0;} |
Java
// Java program to count minimum length// subarray of 1's in a binary array.import java.io.*;class GFG { // Function to count minimum length subarray// of 1's in binary array arr[0..n-1]static int getMinLength(double arr[], int n){ int count = 0; // initialize count int result = Integer.MAX_VALUE; // initialize result for (int i = 0; i < n; i++) { if (arr[i] == 1) { count++; } else { if (count != 0) result = Math.min(result, count); count = 0; } } return result;}// Driver codepublic static void main (String[] args) { double arr[] = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 }; int n = arr.length; System.out.println (getMinLength(arr, n));}}// This code is contributed by ajit. |
Python3
# Python program to count minimum length# subarray of 1's in a binary array.import sys# Function to count minimum length subarray# of 1's in binary array arr[0..n-1]def getMinLength(arr, n): count = 0; # initialize count result = sys.maxsize ; # initialize result for i in range(n): if (arr[i] == 1): count+=1; else: if(count != 0): result = min(result, count); count = 0; return result;# Driver codearr = [ 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 ];n = len(arr);print(getMinLength(arr, n));# This code is contributed by Rajput-Ji |
C#
// C# program to count minimum length// subarray of 1's in a binary array.using System;class GFG{ // Function to count minimum length subarray// of 1's in binary array arr[0..n-1]static int getMinLength(double []arr, int n){ int count = 0; // initialize count int result = int.MaxValue; // initialize result for (int i = 0; i < n; i++) { if (arr[i] == 1) { count++; } else { if (count != 0) result = Math.Min(result, count); count = 0; } } return result;}// Driver codestatic public void Main (){ double []arr = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 }; int n = arr.Length; Console.WriteLine(getMinLength(arr, n));}}// This code is contributed by Tushil.. |
Javascript
<script>// javascript program to count minimum length// subarray of 1's in a binary array. // Function to count minimum length subarray// of 1's in binary array arr[0..n-1]function getMinLength(arr, n){// initialize count var count = 0; // initialize result var result = Number.MAX_VALUE; for (i = 0; i < n; i++) { if (arr[i] == 1) { count++; } else { if (count != 0) result = Math.min(result, count); count = 0; } } return result;}// Driver codevar arr = [ 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1 ];var n = arr.length;document.write(getMinLength(arr, n));// This code is contributed by Amit Katiyar </script> |
Output:
2
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!
