Given an array with only 0's and 1's of size n. We have to find the length of the longest subarray with a count of 1's that is one greater than the count of 0's.
Let's see an example to understand the problem:
Example
Input: arr[ ] = {0, 1, 1, 0, 0, 1}
Output: 5
(Index 1 to 5 is the longest subarray with 1’s one more than the count of 0’s)
Approach
Step 1: Let us consider all the 0’s in the array as ‘-1’.
Step 2: Initialize the sum and max_len as 0.
Step 3: Make a hash table with tuples for (sum, index).
Step 4: Perform the following actions for i = 0 to n-1:
If arr[i] is "0," add "-1" to the total; otherwise, add "1."
Update max_len to i+1 if sum equals 1.
Otherwise, check to see if the sum is stored in the hash table. If it is absent, add it as a pair of (sum, i) values to the hash table.
Verify whether the hash table contains (sum-1) or not. Obtain an index of (sum-1) from the hash table as a result, if it is there. Then update max_len = if max_len is less than (i-index).
Step 5: Return max_len, which is the required answer.
Explanation
A map will be declared. If the condition is met, we will store the value of the sum as well as the current value of an index in that map. Set the sum and max_len values of two variables to 0 each. As we move through the array, we will select each element and determine if arr[i] equals 0. If so, we will add -1 to the sum and store it there; otherwise, if arr[i] is not equal to 0, we will add a positive 1 to the sum and store it there.
The reason for the negative 1 and positive 1 is that we pretend that all 0's are -1 and add them with 1, which ensures that we always get a 0. However, we will look for a positive 1 in the sum, which means we will have one more 1 than the number of 0's.
If we pretend that 0 is -1 and take 1, 0, 1, we will get that 0 with the first two numbers, and with the third number, we can determine that our condition is satisfied. A sub-array of 1's and 0's with one more count of 1 than 0 was obtained. Our condition is resolved. In order to update the length of max_len, we will check whether the sum is equal to 1 in the following algorithmic step.
C++ Code
#include <bits/stdc++.h>
using namespace std;
// function to determine the longest subarray length
int long_Subarray(int arr[], int n)
{
// unordered_map 'm' as hash table
unordered_map<int, int> m;
int sum = 0, max_len = 0;
for (int i = 0; i < n; i++) {
// considering '0' as '-1'
sum += arr[i] == 0 ? -1 : 1;
if (sum == 1)
max_len = i + 1;
else if (m.find(sum) == m.end())
m[sum] = i;
if (m.find(sum - 1) != m.end()) {
// update maxLength
if (max_len < (i - m[sum - 1]))
max_len = i - m[sum - 1];
}
}
return max_len;
}
int main()
{
int arr[] = {1,0,1,0,0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << long_Subarray(arr, n);
return 0;
}
You can also try this code with Online C++ Compiler
O(n), where "n" is the array's total number of elements. We were able to achieve linear time complexity because we used HashMap.
Auxiliary Space
O(n), where "n" is the array's element count. This HashMap achieves linear space complexity because the sum was saved as the key.
Frequently Asked Questions
What is subarray?
A subarray is an array that is contained within the parent array. It is a continuous portion of the array.
What is hashing?
The process of mapping keys and values into a hash table using a hash function is known as hashing.
What is the time complexity of the hashing method solution for the problem of the longest subarray with 1's one more than the count of 0's?
O(n) will be the worst-case time complexity.
What is the space complexity of the hashing method solution for the problem of the longest subarray with 1's one more than the count of 0's?
O(n) will be the worst-case space complexity.
What is a contiguous Subarray?
A contiguous subarray is just a subarray of an array with the requirement that the subarray's elements be in the same exact order as the elements in the parent array.
Conclusion
In this article, we have discussed the famous coding question “Longest Subarray Having Count of 1’s One More Than Count of 0’s” based on the hash map along with its time and space complexity in detail.
117+ registered 