Longest Span with same Sum in two Binary Arrays II

Problem Statement

In the “Longest Span with same Sum in two Binary Arrays II” problem, we have given two binary arrays “a” and “b” with the same size. Write a program to print the longest span with the same sum in two arrays. This can be clearly explained in the below example.

Input Format

The first and only one line containing an integer value n.

Second-line containing n space separated values(0 or 1) of “a”.

The third line also containing n space-separated values(o or 1) of “b”.

Output Format

The first and only one line containing an integer value which denotes the longest span with the same sum in two arrays.

Constraints

• 1<=n<=10^6
• a[i], b[i] must be 0 or 1.

Example

4
0 1 0 1
1 0 0 0

3

Explanation: In the above example, from index 0 to 3 the sum of the elements from index 0 to 3 in the two arrays is the same.

Algorithm for Longest Span with same Sum in two Binary Arrays II

Implementation of the logic is based on the below observations.

• Since there are total n elements, the maximum sum is n for both arrays.
• The difference between two sums varies from -n to n. So there are total 2n + 1 possible value of difference.
• If differences between prefix sums of two arrays become the same at two points, then subarrays between these two points have the same sum.

Now, considering the above three points move to the algorithm part:

1. Create an auxiliary array of size 2n+1 to store starting points of all possible values of differences (Note that possible values of differences vary from -n to n, i.e., there are total 2n+1 possible values)
2. Initialize starting points of all differences as -1.
3. Initialize maxLen as 0 and prefix sums of both arrays as 0, preSum1 = 0, preSum2 = 0
4. Traverse both arrays from i = 0 to n-1.
   1. Update prefix sums: preSum1 += arr1[i], preSum2 += arr2[i]
   2. Compute difference of current prefix sums: curr_diff = preSum1 – preSum2
   3. Find index in diff array: diffIndex = n + curr_diff // curr_diff can be negative and can go till -n
   4. If curr_diff is 0, then i+1 is maxLen so far
   5. Else If curr_diff is seen the first time, i.e., the starting point of current diff is -1, then update starting point as i
   6. Else (curr_diff is NOT seen the first time), then consider i as ending point and find the length of current same sum span. If this length is more, then update maxLen
5. Return maxLen.

Implementation

C++ Program for Longest Span with same Sum in two Binary Arrays II

#include<bits/stdc++.h> 
using namespace std; 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  int b[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<n;i++)
  {
      cin>>b[i];
  }
  int maxLen = 0; 
  int ps1 = 0, ps2 = 0; 
  int temp[2*n+1]; 
  memset(temp, -1, sizeof(temp)); 
  for (int i=0; i<n; i++) 
  { 
    ps1 += a[i]; 
    ps2 += b[i]; 
    int curr_diff = ps1 - ps2; 
    int diff = n + curr_diff; 
    if (curr_diff == 0) 
      maxLen = i+1; 
    else if ( temp[diff] == -1) 
      temp[diff] = i; 
    else
    { 
      int len = i - temp[diff]; 
      if (len > maxLen) 
        maxLen = len; 
    } 
  } 
  cout<<maxLen<<endl; 
  return 0; 
} 

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        int b[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            b[i]=sr.nextInt();
        }
        int maxLen = 0; 
  int ps1 = 0, ps2 = 0; 
  int temp[] = new int [2*n+1]; 
  for(int i=0;i<2*n+1;i++)
        {
            temp[i]=-1;
        }
  for (int i=0; i<n; i++) 
  { 
    ps1 += a[i]; 
    ps2 += b[i]; 
    int curr_diff = ps1 - ps2; 
    int diff = n + curr_diff; 
    if (curr_diff == 0) 
      maxLen = i+1; 
    else if ( temp[diff] == -1) 
      temp[diff] = i; 
    else
    { 
      int len = i - temp[diff]; 
      if (len > maxLen) 
        maxLen = len; 
    } 
  } 
  System.out.println(maxLen); 
    }
}

10
1 0 0 0 1 1 0 1 1 0
0 0 1 0 1 1 0 1 0 0

9

Complexity Analysis for Longest Span with same Sum in two Binary Arrays II

Time Complexity

O(n) where n is the size of the given array “a” or “b”. Here we visit the array and find the difference of prefix sum at a position.

Space Complexity

O(n)  because we declare a temp array which we use to store the index.