Contiguous Array

Difficulty Level Medium
Frequently asked in Amazon MakeMyTrip Morgan Stanley Paytm
Hashing Sliding WindowViews 1460

Given an array consisting of number 0’s and 1’s only. We have to find the length of the longest contiguous sub-array consisting o’s and 1’s equally.

Example

Input

arr = [0,1,0,1,0,0,1]

Output

6

Explanation

The longest contiguous sub-array is marked in red [0,1,0,1,0,0,1] and its length is 6.

Algorithm

  1. Set the value of maxlen to 0.
  2. Use two loops, in the first loop set zer_count to 0, one_count to 0.
  3. If the value of the array at a particular index found to be 0 then increase the zero_count by 1.
  4. Else update and increase the one_count by 1.
  5. At each iteration check if zero_count is equal to one_count, if equal, then find out the bigger no between ( maxlen and j-i+1 )
  6. Return maxlen

Explanation

Our main idea is to find a length of the longest contiguous subarray which has zero’s and one’s only, so our main focus is to find that length.

Therefore, we are going to use nested for loop. In the outer loop, we initialize a value of zero_count and one_count to 0, because after every iteration when it comes out of the inner loop we need fresh values of zero_count and one_count to check all over it again. We are going to iterate over the loop until the length of the array is reached.

Now it is going to check every single value of array, if arr[index] has a value 0 or 1 if it has a value equal to 0 then update and increase the value of zero_count by 1 or if the value of arr[index] founds to be 1, then it updates and increases the value of  one_count by 1.

Now, the next if block is going to check if zero_count is equal to one_count, if equal, then find out the bigger number between maxlen and j-i+1 and stores the bigger number in maxlen.

Example

Suppose array given: arr [ ] ={1,0,0,1,0,1,0}

zero_count=0,one_count=0,maxlen=0

at i=0, => j=i

j=0

at arr[j] not equal to 0, then one_count++, means one_count=1

j=1

At arr[j] equal to 0, then zero_count++, means zero_count=1

At this place next if block is executed, it gives bigger no between maxlen, and j-i+1 and returns 2 in maxlen

j=2

At arr[j] equal to 0, then zero_count++, means zero_count=2

j=3

At arr[j] not equal to 0, then one_count++, means one_count=2

At this place next if block is executed, it gives bigger no between maxlen, and j-i+1 and returns 4 in maxlen.

j=4

At arr[j] equal to 0, then zero_count++, means zero_count=3

j=5

At arr[j] not equal to 0, then one_count++, means one_count=3

At this place next if block is executed, it gives bigger no between maxlen, and j-i+1 and returns 6 in maxlen.

j=6

At arr[j] equal to 0, then zero_count++, means zero_count=4

And it keeps iterating the loop until all the conditions will fail.

And return maxlen as 6.

Implementation

C++ program for Contiguous Array

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}

6

Java program for Contiguous Array

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

Complexity Analysis for Contiguous Array

Time Complexity

O(N*N) where N is the size of the given array.

Space Complexity

O(1) because we don’t use any extra space here.

Reference

Translate »