Problem Statement: Given two binary arrays arr1[] and arr2[] of same size N. Find length of the longest common span [i, j] where j>=i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].
Examples:
Example 1:
Input:
N = 6
Arr1[] = {0, 1, 0, 0, 0, 0}
Arr2[] = {1, 0, 1, 0, 0, 1}
Output: 4
Explanation: the longest span with same sum is from index 1 to 4
Example 2:
Input:
N = 7
arr1[] = {0, 1, 0, 1, 1, 1, 1};
arr2[] = {1, 1, 1, 1, 1, 0, 1};
Output:6
Explanation: the longest span with same sum is from the index 1 to 6
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
We consider the same subarrays for both the arrays one by one, we will compute the sum for all the subarrays, if the sum is the same and the current length is greater than maxLength then we will update our answer
Code :
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSum(int arr1[], int arr2[], int n) {
int ans = 0;
for (int i = 0; i < n; i++) {
int sum1 = 0, sum2 = 0;
for (int j = i; j < n; j++) {
sum1 += arr1[j];
sum2 += arr2[j];
if (sum1 == sum2) {
int len = j - i + 1;
if (len > ans)
ans = len;
}
}
}
return ans;
}
};
int main() {
int n = 6, i;
int arr1[]={0, 1, 0, 0, 0, 0};
int arr2[]={1, 0, 1, 0, 0, 1};
Solution ob;
auto ans = ob.longestCommonSum(arr1, arr2, n);
cout << "The longest common span is: " << ans << "\n";
return 0;
}Output: The longest common span is: 4
Time Complexity: O(n2)
Space Complexity: O(1)
Java Code
import java.util.*;
class Solution {
static int longestCommonSum(int arr1[], int arr2[], int n) {
int ans = 0;
for (int i = 0; i < n; i++) {
int sum1 = 0, sum2 = 0;
for (int j = i; j < n; j++) {
sum1 = sum1 + arr1[j];
sum2 = sum2 + arr2[j];
if (sum1 == sum2) {
int len = j - i + 1;
if (len > ans)
ans = len;
}
}
}
return ans;
}
public static void main(String args[]) {
int n = 6, i;
int arr1[]={0, 1, 0, 0, 0, 0};
int arr2[]={1, 0, 1, 0, 0, 1};
int ans = longestCommonSum(arr1, arr2, n);
System.out.println("The longest common span is: " + ans);
}
}Output: The longest common span is: 4
Time Complexity: O(n2)
Space Complexity: O(1)
Solution 2: Using an auxiliary array
- Calculate prefix sum for both the arrays -i.e. presum1,presum2, since it is a binary array the max sum can be n
- Max prefix sum can be n-0 i.e n , Min prefix sum can be 0-n = -n
- So prefix sum can be from range -n to +n, so there are 2n+1 values of differences
- If differences between prefix sums of two arrays become same at two points, then subarrays between these two points have same sum.
- So create an array of size 2n+1 to store all possible difference //initialise this array with -1
- We will traverse both the arrays and update our respective prefix sums presum1+=arr[ i ] presum2 +=arr2[ i ]
- Now computing the difference between them ,diff =presum1-presum2
- The difference array diff will be from -n to +n , since we don’t want to deal with negative indices , we will add +n for getting the indices of difference array , so diffIndex=n+curr_diff
- If curr_len = 0 then i+1 will be our answer as (difference is 0 , presum of both the arrays would be same so , the length from the start would be the ans)
- Else If curr_diff is seen first time, i.e starting point of current diff is -1, then update starting point as i so, diff[diffIndex]=i
- Else curr_diff is NOT seen first time then consider i as ending point and find length of current same sum span . i.e i – diff[diffIndex]. If this length is more, then update ans
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSum(int arr1[], int arr2[], int n) {
int ans = 0;
int diff[2 * n + 1];
int presum1 = 0;
int presum2 = 0;
for (int i = 0; i < 2 * n + 1; i++) diff[i] = -1;
for (int i = 0; i < n; i++) {
presum1 += arr1[i];
presum2 += arr2[i];
int currdiff = presum1 - presum2;
int diffindex = n + currdiff;
if (currdiff == 0) ans = i + 1;
else if (diff[diffindex] == -1) diff[diffindex] = i;
else { //currdiff is already seen
int len = i - diff[diffindex];
if (len > ans) ans = len;
}
}
return ans;
}
};
int main() {
int n=6, i;
int arr1[]={0, 1, 0, 0, 0, 0};
int arr2[]={1, 0, 1, 0, 0, 1};
Solution ob;
auto ans = ob.longestCommonSum(arr1, arr2, n);
cout <<"The longest common span is: "<<ans << "\n";
return 0;
}
Output: The longest common span is: 4
Time Complexity: O(n) as we are traversing both the arrays only once
Space Complexity: O(n) as we are creating a difference array
Java Code
import java.util.*;
class Solution {
static int longestCommonSum(int arr1[], int arr2[], int n) {
int ans = 0;
int diff[]=new int[2 * n + 1];
int presum1 = 0;
int presum2 = 0;
for (int i = 0; i < 2 * n + 1; i++) diff[i] = -1;
for (int i = 0; i < n; i++) {
presum1 += arr1[i];
presum2 += arr2[i];
int currdiff = presum1 - presum2;
int diffindex = n + currdiff;
if (currdiff == 0) ans = i + 1;
else if (diff[diffindex] == -1) diff[diffindex] = i;
else { //currdiff is already seen
int len = i - diff[diffindex];
if (len > ans) ans = len;
}
}
return ans;
}
public static void main(String args[]) {
int n=6, i;
int arr1[]={0, 1, 0, 0, 0, 0};
int arr2[]={1, 0, 1, 0, 0, 1};
int ans =longestCommonSum(arr1, arr2, n);
System.out.println("The longest common span is: "+ans);
}
}Output: The longest common span is: 4
Time Complexity: O(n) as we are traversing both the arrays only once
Space Complexity: O(n) as we are creating a difference array
Solution 3: Using hash map
In this, we don’t need any prefix sum of both the arrays.
- We simply have to maintain one array which would have the difference of the current element’s values i.e arr[ i ] =arr1[ i ] – arr2[ i ]
- Maintain prefix sum of this arr
- If sum = 0 ,it would mean that both the arrays would have equal no. of 0s and 1s so ans=i+1
- If the sum is before i.e if its already present in the hash map then we will update the ans
- Else we will push the sum into hashmap
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSum(int arr1[], int arr2[], int n) {
unordered_map < int, int > mymap;
int arr[n];
int sum = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
arr[i] = arr1[i] - arr2[i];
}
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == 0) ans = i + 1;
else if (mymap.find(sum) != mymap.end()) ans = max(ans, i - mymap[sum]);
else mymap[sum] = i;
}
return ans;
}
};
int main() {
int n=6, i;
int arr1[]={0, 1, 0, 0, 0, 0};
int arr2[]={1, 0, 1, 0, 0, 1};
Solution ob;
auto ans = ob.longestCommonSum(arr1, arr2, n);
cout <<"The longest common span is: "<<ans << "\n";
return 0;
}
Output: The longest common span is: 4
Time Complexity: O(n) as we are traversing both the arrays only once
Space Complexity: O(n) as we are creating an array and maintaining a hashmap
Java Code
import java.util.*;
class Solution {
static int longestCommonSum(int arr1[], int arr2[], int n) {
HashMap <Integer,Integer > mymap=new HashMap<>();;
int arr[]=new int[n];
int sum = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
arr[i] = arr1[i] - arr2[i];
}
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == 0) ans = i + 1;
else if (mymap.containsKey(sum))
ans = Math.max(ans, i - mymap.get(sum));
else mymap.put(sum,i);
}
return ans;
}
public static void main(String args[]) {
int n=6, i;
int arr1[]={0, 1, 0, 0, 0, 0};
int arr2[]={1, 0, 1, 0, 0, 1};
int ans =longestCommonSum(arr1, arr2, n);
System.out.println("The longest common span is: "+ans);
}
}Output: The longest common span is: 4
Time Complexity: O(n) as we are traversing both the arrays only once
Space Complexity: O(n) as we are creating an array and maintaining a hashmap
Special thanks to Pawan Jumani for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article