Length of longest continuous sequence with same sum in given binary arrays

Given two Boolean arrays X and Y, find the length of longest continuous sequence that starts and ends at same index in both arrays and have same sum. In other words, find max(j-i+1) for every j >= i where sum of sub-array X[i, j] is equal to sum of sub-array Y[i, j].

 

For example, consider below Boolean arrays X[] and Y[]


  X: {0, 0, 1, 1, 1, 1}
  Y: {0, 1, 1, 0, 1, 0}
 

The length of longest continuous sequence with same sum is 5 as


  X[0, 4]: {0, 0, 1, 1, 1}      (sum = 3)
  Y[0, 4]: {0, 1, 1, 0, 1}      (sum = 3)

 

Naive solution would be to consider every sub-array [i, j] where (j > i) and check if sum of X[i, j] is equal to sum of Y[i, j] or not. If sum is found to be equal and length of the sub-array is more than maximum found so far, we update the result. The time complexity of above solution is O(n2) assuming that sum of each sub-array is computed in constant time.

 

We can solve this problem in linear time. The idea is to traverse the array and maintain sum of elements of X[] and Y[] till current index and calculate difference between the two sums.

  • If the difference is seen for the first time, then we store the difference and current index in a map.
     
  • If difference is seen before and index of previous occurrence is i, then we have found sub-arrays X[i+1, j] and Y[i+1, j] ending at current index j, whose sum of elements is equal. If length of the sub-array is more than maximum found so far, we update the result.

 
How does this works?
 


Claim: If difference is seen before and index of previous occurrence is i,
       then X[i+1, j] = Y[i+1, j]

 
We can write previous difference di = X[0, i] – Y[0, i]

Similarly, current difference dj = X[0, j] – Y[0, j] or
  dj = (X[0, i] + X[i+1, j]) – (Y[0, i] + Y[i+1, j])
 

If difference is seen before i.e. (dj = di), then

  (X[0, i] + X[i+1, j]) – (Y[0, i] + Y[i+1, j]) = X[0, i] – Y[0, i]
  X[i+1, j] – Y[i+1, j] = 0 or
  X[i+1, j] == Y[i+1, j]

C++

Download   Run Code

Output:

The length of longest continuous sequence with same sum is 5

Java

Download   Run Code

Output:

The length of longest continuous sequence with same sum is 5

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
AllergicToBitches
Guest

Awesome solution..