Longest subarray having count of 1s one more than count of 0s
Given an array of size n containing 0’s and 1’s only. The problem is to find the length of the longest subarray having count of 1’s one more than count of 0’s.
Examples:
Input : arr = {0, 1, 1, 0, 0, 1}
Output : 5
From index 1 to 5.
Input : arr[] = {1, 0, 0, 1, 0}
Output : 1
Approach: Following are the steps:
- Consider all the 0’s in the array as ‘-1’.
- Initialize sum = 0 and maxLen = 0.
- Create a hash table having (sum, index) tuples.
- For i = 0 to n-1, perform the following steps:
- If arr[i] is ‘0’ accumulate ‘-1’ to sum else accumulate ‘1’ to sum.
- If sum >= 1, update maxLen = i+1.
- Else check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
- Check if (sum-1) is present in the hash table or not. if present, then obtain index of (sum-1) from the hash table as index. Now check if maxLen is less than (i-index), then update maxLen = (i-index).
- Return maxLen.
Below is the implementation of the above approach:
// C++ implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
#include <bits/stdc++.h>
using namespace std;
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
int lenOfLongSubarr(int arr[], int n)
{
// unordered_map 'um' implemented as
// hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// consider '0' as '-1'
sum += arr[i] == 0 ? -1 : 1;
// when subarray starts form index '0'
if (sum >= 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-1' is present in 'um'
// or not
if (um.find(sum - 1) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - 1]))
maxLen = i - um[sum - 1];
}
}
// required maximum length
return maxLen;
}
// Driver program to test above
int main()
{
int arr[] = { 0, 1, 1, 0, 0, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length = " << lenOfLongSubarr(arr, n);
return 0;
}
// Java implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
import java.util.*;
class GFG {
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
static int lenOfLongSubarr(int arr[], int n)
{
// unordered_map 'um' implemented as
// hash table
HashMap<Integer, Integer> um
= new HashMap<Integer, Integer>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// consider '0' as '-1'
sum += arr[i] == 0 ? -1 : 1;
// when subarray starts from index '0'
if (sum == 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (!um.containsKey(sum))
um.put(sum, i);
// check if 'sum-1' is present in 'um'
// or not
if (um.containsKey(sum - 1)) {
// update maxLength
if (maxLen < (i - um.get(sum - 1)))
maxLen = i - um.get(sum - 1);
}
}
// required maximum length
return maxLen;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 0, 1, 1, 0, 0, 1 };
int n = arr.length;
System.out.println("Length = "
+ lenOfLongSubarr(arr, n));
}
}
// This code is contributed by Princi Singh
# Python 3 implementation to find the length of
# longest subarray having count of 1's one
# more than count of 0's
# function to find the length of longest
# subarray having count of 1's one more
# than count of 0's
def lenOfLongSubarr(arr, n):
# unordered_map 'um' implemented as
# hash table
um = {}
sum = 0
maxLen = 0
# traverse the given array
for i in range(n):
# consider '0' as '-1'
if arr[i] == 0:
sum += -1
else:
sum += 1
# when subarray starts form index '0'
if (sum == 1):
maxLen = i + 1
# make an entry for 'sum' if it is
# not present in 'um'
elif (sum not in um):
um[sum] = i
# check if 'sum-1' is present in 'um'
# or not
if ((sum - 1) in um):
# update maxLength
if (maxLen < (i - um[sum - 1])):
maxLen = i - um[sum - 1]
# required maximum length
return maxLen
# Driver code
if __name__ == '__main__':
arr = [0, 1, 1, 0, 0, 1]
n = len(arr)
print("Length =", lenOfLongSubarr(arr, n))
# This code is contributed by
# Surendra_Gangwar
// C# implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
using System;
using System.Collections.Generic;
class GFG {
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
static int lenOfLongSubarr(int[] arr, int n)
{
// unordered_map 'um' implemented as
// hash table
Dictionary<int, int> um
= new Dictionary<int, int>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// consider '0' as '-1'
sum += arr[i] == 0 ? -1 : 1;
// when subarray starts form index '0'
if (sum == 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (!um.ContainsKey(sum))
um.Add(sum, i);
// check if 'sum-1' is present in 'um'
// or not
if (um.ContainsKey(sum - 1)) {
// update maxLength
if (maxLen < (i - um[sum - 1]))
maxLen = i - um[sum - 1];
}
}
// required maximum length
return maxLen;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 0, 1, 1, 0, 0, 1 };
int n = arr.Length;
Console.WriteLine("Length = "
+ lenOfLongSubarr(arr, n));
}
}
// This code is contributed by Rajput-Ji
<script>
// Javascript implementation to find the length of
// longest subarray having count of 1's one
// more than count of 0's
// function to find the length of longest
// subarray having count of 1's one more
// than count of 0's
function lenOfLongSubarr(arr, n)
{
// unordered_map 'um' implemented as
// hash table
var um = new Map();
var sum = 0, maxLen = 0;
// traverse the given array
for (var i = 0; i < n; i++) {
// consider '0' as '-1'
sum += arr[i] == 0 ? -1 : 1;
// when subarray starts form index '0'
if (sum == 1)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
else if (!um.has(sum))
um.set(sum, i);
// check if 'sum-1' is present in 'um'
// or not
if (um.has(sum - 1)) {
// update maxLength
if (maxLen < (i - um.get(sum - 1)))
maxLen = i - um.get(sum - 1);
}
}
// required maximum length
return maxLen;
}
// Driver program to test above
var arr = [0, 1, 1, 0, 0, 1];
var n = arr.length;
document.write( "Length = "
+ lenOfLongSubarr(arr, n));
// This code is contributed by itsok.
</script>
Output
Length = 5
Time Complexity: O(n)
Auxiliary Space: O(n)
using Brute Force:
Approach:
One way to solve this problem is to iterate through all possible subarrays and count the number of ones and zeros in each subarray. Then, we can check if the count of ones is one more than the count of zeros and keep track of the maximum subarray length that satisfies this condition.
Initialize the maximum subarray length to zero.
Iterate through all possible starting indices of the subarrays.
For each starting index, initialize the count of ones and zeros to zero.
Iterate through all possible ending indices of the subarrays.
For each ending index, update the counts of ones and zeros based on the value at the current index.
Check if the count of ones is one more than the count of zeros.
If the condition is satisfied, update the maximum subarray length.
Return the maximum subarray length.
#include <bits/stdc++.h>
using namespace std;
// Added by ~Nikunj Sonigara
int longestSubarray(vector<int>& arr) {
int n = arr.size();
int maxLen = 0;
for (int i = 0; i < n; i++) {
int count0 = 0;
int count1 = 0;
for (int j = i; j < n; j++) {
if (arr[j] == 0) {
count0++;
} else {
count1++;
}
if (count1 == count0 + 1) {
maxLen = max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
int main() {
vector<int> arr1 = {0, 1, 1, 0, 0, 1};
cout << longestSubarray(arr1) << endl; // Output: 5
vector<int> arr2 = {1, 0, 0, 1, 0};
cout << longestSubarray(arr2) << endl; // Output: 1
return 0;
}
import java.util.*;
// Added by ~Nikunj Sonigara
public class Main {
public static int longestSubarray(List<Integer> arr) {
int n = arr.size();
int maxLen = 0;
for (int i = 0; i < n; i++) {
int count0 = 0;
int count1 = 0;
for (int j = i; j < n; j++) {
if (arr.get(j) == 0) {
count0++;
} else {
count1++;
}
if (count1 == count0 + 1) {
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
public static void main(String[] args) {
List<Integer> arr1 = new ArrayList<>();
arr1.add(0);
arr1.add(1);
arr1.add(1);
arr1.add(0);
arr1.add(0);
arr1.add(1);
System.out.println(longestSubarray(arr1)); // Output: 5
List<Integer> arr2 = new ArrayList<>();
arr2.add(1);
arr2.add(0);
arr2.add(0);
arr2.add(1);
arr2.add(0);
System.out.println(longestSubarray(arr2)); // Output: 1
}
}
def longest_subarray(arr):
n = len(arr)
max_len = 0
for i in range(n):
count_0 = 0
count_1 = 0
for j in range(i, n):
if arr[j] == 0:
count_0 += 1
else:
count_1 += 1
if count_1 == count_0 + 1:
max_len = max(max_len, j - i + 1)
return max_len
arr = [0, 1, 1, 0, 0, 1]
print(longest_subarray(arr)) # Output: 5
arr = [1, 0, 0, 1, 0]
print(longest_subarray(arr)) # Output: 1
using System;
using System.Collections.Generic;
class Program {
// Function to find the length of the longest subarray
static int LongestSubarray(List<int> arr)
{
int n = arr.Count;
int maxLen = 0;
// Iterate through the array
for (int i = 0; i < n; i++) {
int count0 = 0;
int count1 = 0;
// Consider subarrays starting from index i
for (int j = i; j < n; j++) {
// Count the number of 0s and 1s in the
// subarray
if (arr[j] == 0) {
count0++;
}
else {
count1++;
}
// Check if the subarray has one more 1 than
// 0
if (count1 == count0 + 1) {
// Update the maximum length if the
// condition is met
maxLen = Math.Max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
static void Main()
{
List<int> arr1 = new List<int>{ 0, 1, 1, 0, 0, 1 };
Console.WriteLine(
LongestSubarray(arr1)); // Output: 5
List<int> arr2 = new List<int>{ 1, 0, 0, 1, 0 };
Console.WriteLine(
LongestSubarray(arr2)); // Output: 1
}
}
// Added by ~Nikunj Sonigara
function longestSubarray(arr) {
const n = arr.length;
let maxLen = 0;
for (let i = 0; i < n; i++) {
let count0 = 0;
let count1 = 0;
for (let j = i; j < n; j++) {
if (arr[j] === 0) {
count0++;
} else {
count1++;
}
if (count1 === count0 + 1) {
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
const arr1 = [0, 1, 1, 0, 0, 1];
console.log(longestSubarray(arr1)); // Output: 5
const arr2 = [1, 0, 0, 1, 0];
console.log(longestSubarray(arr2)); // Output: 1
Output
5 1
Time Complexity: O(n^2)
Space Complexity: O(1)
Contact Us