Tutorialspoint.dev

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:

  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 <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;
}

Output:

Length = 5

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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter