Longest Subarray with an equal 0s and 1s

Problem statement: Given an array containing only 0s and 1s, find the largest subarray which contains an equal no of 0s and 1s.

Examples:

Example 1:
Input: arr[] = {1, 1, 1, 1}

Output: No such subarray

Example 2:
Input: arr[] = {0, 0, 1, 1, 0}

Output: 0 to 3 Or 1 to 4

Example 3:
Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 

Starting index and ending index is given of 
the longest subarray with equal 1's and 0's

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Brute Force.

Approach:

Use two nested loops.
Take variable sum = 0, at its start, in which we will take our cumulative sum from all the sub-arrays.
The outer loop picks a starting point i = 0 and the inner loop will start from j = i + 1.
Start taking the sum from all the subarrays, whenever we get sum value = 0, it means it has an equal number of 1s and 0s.
Now compare every size with the longest subarray(maxlen variable), if we got the max size than the longest subarray we will update our subarray in the maxlen variable.
Return the longest subarray maxlen startIndex and Size.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

int findSubArray(int nums[], int n) {
  int sum = 0;
  int maxlen = -1, startindex;

  // Pick a starting point as i
  for (int i = 0; i < n - 1; i++) {
    sum = (nums[i] == 0) ? -1 : 1;

    // Consider all subarrays starting from i
    for (int j = i + 1; j < n; j++) {
      (nums[j] == 0) ? (sum += -1) : (sum += 1);

      // If this is a 0 sum subarray, then
      // compare it with maximum size subarray
      if (sum == 0 && maxlen < j - i + 1) {
        maxlen = j - i + 1;
        startindex = i;
      }
    }
  }
  if (maxlen == -1)
    cout << "No such subarray";
  else
    cout << "The length of the longest subarray is: " << maxlen;
}

/* Driver code*/
int main() {
  int arr[] = { 1, 0, 0, 1, 0, 0, 1 };
  int size = sizeof(arr) / sizeof(arr[0]);

  findSubArray(arr, size);
  return 0;
}

Output: The length of the longest subarray is: 4

Time Complexity: O(N^2) as We consider every possible subarray by traversing over the complete array for every start point possible.

Space Complexity: O(1) as Only two variables zeros and ones are required

Java Code

class LongestSubArray {

  void findSubArray(int nums[], int n) {
    int sum = 0;
    int maxlen = -1, startindex = 0;
    int endindex = 0;

    // Pick a starting point as i

    for (int i = 0; i < n - 1; i++) {
      sum = (nums[i] == 0) ? -1 : 1;

      // Consider all subarrays starting from i

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

        // If this is a 0 sum subarray, then
        // compare it with maximum size subarray

        if (sum == 0 && maxlen < j - i + 1) {
          maxlen = j - i + 1;
          startindex = i;
        }
      }
    }

    if (maxlen == -1)
      System.out.println("No such subarray");
    else
      System.out.println("The length of the longest subarray is: " + maxlen);
  }

  /* Driver program to test the above functions */

  public static void main(String[] args) {
    LongestSubArray sub;
    sub = new LongestSubArray();
    int arr[] = { 1, 0, 0, 1, 0, 0, 1  };
    int size = arr.length;
    sub.findSubArray(arr, size);
  }
}

Output: start index 0 to end index 3

Time Complexity: O(N^2) as We consider every possible subarray by traversing over the complete array for every start point possible.

Space Complexity: O(1) as Only two variables zeros and ones are required

Solution 2: Optimal Solution(Hashmap)

Approach:

Convert all the “0” to “-1” in the example, so that we get something like :-

[0, 0,1,0,1,0]. If you see this, the problem is somewhat like returning the longest subarray length whose sum is “ZERO”.

As the question is telling us to return same/equal numbers of zeros and ones.
So, that means the same as well there will be equal no. of 1 & -1 .
sum 1 + (-1) = 0,we conclude that we need to return that subarray length, whose sum is 0 with the longest subarray.

In our hashMap, we will have key & value.

At start max = 0 and so index will be -1 and cumulative sum = 0.
We move further to get a max of 1. And in our hashmap for reference we put the key 0 -> -1 value.
We will check in our key value pair if we have the pair of 1? As at index 0 ->0
No there is no pair of 1 we will move forward by adding sum = -1 and -1(at 1st index) = sum = -1+ -1 = -2
Move forward and check the index(2) we got 1 that means sum = -2 + 1 = -1.
Since we already have -1 in our map, that means there is a subarray and length = 2 (index(2) – index(0)) ,subarray = [0,1]
Now moving further & at index 3 we got a gain of 1 as Our cumulative sum is = -1 + -1 = -2 And if we look at hashmap -2 is already present there is a subarray, length index(3-2) = 1 will not update the length here 1 < 2,
At index 4 we have 1 so sum = -2 + 1 = -1 and -1 is already in the hashmap at index 1 and 0 length from 0 to 4 = index(4 – 0) = 4 another one is index(4 – 3) = 1 max-length = 4
Finally, our max-length = 4.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

int findMaxLength(int nums[], int n) {
  map < int, int > map;
  map.insert({0,-1});
  int maxlen = 0, count = 0;
  for (int i = 0; i < n; i++) {
    count = count + (nums[i] == 1 ? 1 : -1);
    if (map.find(count) != map.end()) {
      maxlen = max(maxlen, i - map[count]);
    } else {
      map.insert({count,i});
    }
  }
  cout << "The length of the longest subarray is: " << maxlen;
}

/* Driver code*/
int main() {
  int arr[] = { 1, 0, 0, 1, 0, 0, 1 };
  int size = sizeof(arr) / sizeof(arr[0]);
  findMaxLength(arr, size);
  return 0;
}

Output: The length of the longest subarray is: 4

Time Complexity: O(N) where n is the size of an array.

Space Complexity: O(n) as map used.

Java Code

import java.util.*;
class LongestSubArray {

  public static void findMaxLength(int[] arr) {

    // write your code here
    int max = 0;

    HashMap < Integer, Integer > map = new HashMap < > ();
    map.put(0, -1); // at the starting we will put -1 for 0

    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == 0) {
        sum += -1; //whenever we have 0 = -1
      } else if (arr[i] == 1) {
        sum += +1; // whenever we have 1 = 1
      }
      if (map.containsKey(sum)) {
        int idx = map.get(sum);
        int length = i - idx;
        if (length > max) {
          max = length;
        }
      } else {
        map.put(sum, i);
      }

    }
    System.out.println("The length of the longest subarray is: " + max);

  }

  public static void main(String[] args) {
    int arr[] = { 1, 0, 0, 1, 0, 0, 1  };
    int size = arr.length;
    findMaxLength(arr);
  }
}

Output: The length of the longest subarray is: 4

Time Complexity: O(N) where n is the size of an array.

Space Complexity: O(n) as map used.

Special thanks to Amisha Kumari for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article