Longest Span in two Binary Arrays

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Find longest span [i..j] where count of 1s in both arrays are equal. Difference prefix sum + hashmap.

Algorithm

1Compute running difference (count1_in_A - count1_in_B). Find max span with same difference value using first occurrence map.

Common Pitfalls

•Reduce to "longest subarray with sum 0" by encoding as +1/-1 per array and tracking difference.

Longest Span in two Binary Arrays.java

Java

// Approach: Compute difference array (a[i]-b[i]). Find longest subarray with sum 0 using prefix sum HashMap.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public int longestCommonSum(int[] a1, int[] a2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        int ans = 0;
        
        for (int i = 0; i < a1.length; i++) {
            sum += (a1[i] - a2[i]);
            map.put(sum, map.getOrDefault(sum, i));
            ans = Math.max(ans, i - map.get(sum));
        }

        return ans;
    }
}

Was this solution helpful?