Longest Subarray Having Count of 1s One More than Count of 0s

Difficulty Level Easy
Frequently asked in Accenture Amazon DE Shaw Samsung
Array HashViews 2677

We have given an array of integers. An array contains 1’s and 0’s only. The problem statement asks to find out the length of the longest Sub-Array which having the quantity of 1’s digit is just one more than the count of 0’s in a sub-array.

Example

Input:

arr[] = {1,0,1,1,0,0,0}

Output:

5

Explanation:

From 0 to 4 index, {1, 0, 1, 1, 0}, there are three 1’s and two 0’s. Just one more count of 1’s than 0’s.

Input:

arr[] = {1,0,1,0,0}

Output:

3

Explanation:

From 0 to 2 index, {1, 0, 1}, there are two 1’s and one 0’s. Just one more count of 1’s than 0’s.

Algorithm

  1. Declare a map.
  2. Set the sum and outputLength to 0.
  3. Traverse the array, while i=0 to i < n.
    1. Check if arr [ i ] is equal to 0 if true then add -1 to sum.
    2. Else add +1 to sum.
    3. Check if the sum is equal to 1, then increase the value of outputLength by 1.
    4. Else, check if a map doesn’t contain the sum if true then put the sum and current value of i to the map along with the sum.
    5. Check if a map contains the (sum-1).
    6. If outputLength is less than the i-index(sum’s value in the map).
      1. If true, then update the outputLength to i-index.
  4. Return output length.

Explanation

We will declare a map. In that map, we are going to store the value of sum and the current value of an index, if the condition satisfies. Take two variables and set sum to 0 and outputLength to 0. While traversing the array, we will pick each element of an array, and check if arr[i] is equal to 0, if it is found to be equal, we will add -1 to sum and store it to sum, else if we have not found to be 0, we will be adding the positive 1 to sum and store it to sum.

The reason behind that negative 1 and positive 1 is, we are pretending all 0’s to -1 and add them with 1, so we will get the 0 always. But we will check for positive 1 in sum, which indicates that we will have one extra 1 then the count of 0’s.

Suppose, we will take 1, 0, 1 if we are pretending 0 as -1, we will get that 0 with first 2 numbers, and with the third number, we can found that our condition is fulfilled. We got a sub-array of 1’s and 0’s with one extra count of 1 than 0. We get our condition satisfied. That’s why we will be looking for if the sum is equal to 1 in the next step of an algorithm and will be updating the length of outputLength. In the last, if the statement, if we get the new output length, we need to update the previous one with the current outputLength and we will return outputLength.

Implementation

C++ program for Longest Subarray Having Count of 1s One More than Count of 0s

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}

Length of the longest Sub-Array : 5

Java program for Longest Subarray Having Count of 1s One More than Count of 0s

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

Complexity Analysis for Longest Subarray Having Count of 1s One More than Count of 0s

Time Complexity

O(n) where “n”  is the number of elements in the array.

Space Complexity

O(n) where “n”  is the number of elements in the array.

Translate »