# 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Following are the steps:

1. Consider all the 0’s in the array as ‘-1’.
2. Initialize sum = 0 and maxLen = 0.
3. Create a hash table having (sum, index) tuples.
4. For i = 0 to n-1, perform the following steps:
1. If arr[i] is ‘0’ accumulate ‘-1’ to sum else accumulate ‘1’ to sum.
2. If sum == 1, update maxLen = i+1.
3. 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.
4. 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).
5. Return maxLen.
 `// C++ implementation to find the length of ` `// longest subarray having count of 1's one ` `// more than count of 0's ` `#include ` `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; ` `} `

Output:

```Length = 5
```

Time Complexity: O(n)
Auxiliary Space: O(n)

## tags:

Arrays Hash Arrays Hash