longest common span of same sum

Tushar Roy · Tushar Roy · commit f7bb8fec5376 · 2015-12-29T11:43:22.000-06:00
diff --git a/python/array/longestsamesumspan.py b/python/array/longestsamesumspan.py
@@ -0,0 +1,27 @@
+# http://www.geeksforgeeks.org/longest-span-sum-two-binary-arrays/
+
+def longest_span(input1, input2):
+    if len(input1) != len(input2):
+        raise ValueError;
+
+    diff = {}
+    prefix1 = 0
+    prefix2 = 0
+    max_span = 0
+    for i in range(len(input1)):
+        prefix1 += input1[i]
+        prefix2 += input2[i]
+        curr_diff = prefix1 - prefix2
+        if curr_diff in diff:
+            max_span = max(max_span, i - diff[curr_diff])
+        else:
+            diff[curr_diff] = i
+    return max_span
+
+if __name__ == '__main__':
+    input1 = [0, 1, 0, 1, 1, 1, 1]
+    input2 = [1, 1, 1, 1, 1, 0, 1]
+
+    print(longest_span(input1, input2))
+    
+    
diff --git a/src/com/interview/array/LongestSameSumSpan.java b/src/com/interview/array/LongestSameSumSpan.java
@@ -0,0 +1,48 @@
+package com.interview.array;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Date 12/29/2015
+ * @author Tushar Roy
+ *
+ * Give two arrays of same size consisting of 0s and 1s find span (i, j) such that
+ * sum of input1[i..j] = sum of input2[i..j]
+ *
+ * Time complexity O(n)
+ * Space complexity O(n)
+ *
+ * http://www.geeksforgeeks.org/longest-span-sum-two-binary-arrays/
+ */
+public class LongestSameSumSpan {
+
+    public int longestSpan(int input1[], int input2[]) {
+        if (input1.length != input2.length) {
+            throw new IllegalArgumentException("Not same length input");
+        }
+        Map<Integer, Integer> diff = new HashMap<>();
+        int prefix1 = 0, prefix2 = 0;
+        int maxSpan = 0;
+        for (int i = 0; i < input1.length ; i++) {
+            prefix1 += input1[i];
+            prefix2 += input2[i];
+            int currDiff = prefix1 - prefix2;
+            if (diff.containsKey(currDiff)) {
+                maxSpan = Math.max(maxSpan, i - diff.get(currDiff));
+            } else {
+                diff.put(currDiff, i);
+            }
+        }
+        return maxSpan;
+    }
+
+    public static void main(String args[]) {
+        int input1[] = {0, 1, 0, 1, 1, 1, 1};
+        int input2[] = {1, 1, 1, 1, 1, 0, 1};
+
+        LongestSameSumSpan lsss = new LongestSameSumSpan();
+        System.out.print(lsss.longestSpan(input1, input2));
+    }
+
+}
