flip 0s to get max consecutive 1s in array

Tushar Roy · Tushar Roy · commit 403b04b858f6 · 2015-12-29T18:19:32.000-06:00
diff --git a/python/array/flip0smaximum1s.py b/python/array/flip0smaximum1s.py
@@ -0,0 +1,23 @@
+# http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/
+
+def flip_0s_to_maximize_consecutive_1s(input, flips_allowed):
+    window_start = 0
+    count_zero = 0
+    result = 0
+    for i in range(len(input)):
+        if input[i] == 1:
+            result = max(result, i - window_start + 1)
+        else:
+            if count_zero < flips_allowed:
+                count_zero = count_zero + 1
+            else:
+                while True:
+                    if input[window_start] == 0:
+                        window_start = window_start + 1
+                        break
+                    window_start = window_start + 1
+    return result
+    
+if __name__ == '__main__':
+    input = [0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]
+    print(flip_0s_to_maximize_consecutive_1s(input, 1))
diff --git a/src/com/interview/array/Flip0sMaximum1s.java b/src/com/interview/array/Flip0sMaximum1s.java
@@ -0,0 +1,47 @@
+package com.interview.array;
+
+/**
+ * Date 12/29/2015
+ * @author Tushar Roy
+ *
+ * Given input array of 0s and 1s and number of flips allowed from 0 to 1, what is maximum consecutive 1s we can have
+ * in array
+ *
+ * Time complexity - O(n)
+ * Space complexity - O(1)
+ *
+ * http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/
+ */
+public class Flip0sMaximum1s {
+
+    public int flip0sToMaximizeConsecutive1s(int input[], int flipsAllowed) {
+
+        int windowStart = 0;
+        int countZero = 0;
+        int result = 0;
+        for (int i = 0 ; i < input.length; i++) {
+            if (input[i] == 1) {
+                result = Math.max(result, i - windowStart + 1);
+            } else {
+                if (countZero < flipsAllowed) {
+                    countZero++;
+                } else {
+                    while(true) {
+                        if (input[windowStart] == 0) {
+                            windowStart++;
+                            break;
+                        }
+                        windowStart++;
+                    }
+                }
+            }
+        }
+        return result;
+    }
+
+    public static void main(String args[]) {
+        int input[] = {0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1};
+        Flip0sMaximum1s fm = new Flip0sMaximum1s();
+        System.out.print(fm.flip0sToMaximizeConsecutive1s(input, 1));
+    }
+}
