LeetCode 1004 - Max Consecutive Ones III

Related:
LeetCode 485 - Max Consecutive Ones
LeetCode 487 - Max Consecutive Ones II

LeetCode 1004 - Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s. 

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1 

https://leetcode.com/problems/max-consecutive-ones-iii/discuss/247543/O(n)-Java-Solution-using-sliding-window

I think the question is a simplified version of 424. Longest Repeating Character Replacement
My solution is changed from Java 12 lines O(n) sliding window solution with explanation

public int longestOnes(int[] A, int K) {
        int zeroCount=0,start=0,res=0;
        for(int end=0;end<A.length;end++){
            if(A[end] == 0) zeroCount++;
            while(zeroCount > K){
                if(A[start] == 0) zeroCount--;
                start++;
            }
            res=Math.max(res,end-start+1);
        }
        return res;
    }

https://leetcode.com/problems/max-consecutive-ones-iii/discuss/247564/JavaC%2B%2BPython-Sliding-Window

Translation: Find the longest subarray with at most K zeros.
Similar as all "Find the longest subarray" problems.

Explanation

For each A[j], try to find the longest subarray.
If A[i] ~ A[j] has zeros <= K, we continue to increment j.
If A[i] ~ A[j] has zeros > K, we increment i.

    public int longestOnes(int[] A, int K) {
        int res = 0, i = 0;
        for (int j = 0; j < A.length; ++j) {
            if (A[j] == 0) K--;
            if (K < 0 && A[i++] == 0) K++;
            res = Math.max(res, j - i + 1);
        }
        return res;
    }

X. https://leetcode.com/problems/max-consecutive-ones-iii/discuss/248215/java-dynamic-programming-version
http://www.noteanddata.com/leetcode-1004-Max-Consecutive-Ones-III-java-solution-note.html


https://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/

    static void findZeroes(int m)

    {

        // Left and right indexes of current window

        int wL = 0, wR = 0; 

      

        // Left index and size of the widest window 

        int bestL = 0, bestWindow = 0; 

      

        // Count of zeroes in current window

        int zeroCount = 0; 

      

        // While right boundary of current window doesn't cross 

        // right end

        while (wR < arr.length)

        {

            // If zero count of current window is less than m,

            // widen the window toward right

            if (zeroCount <= m)

            {

                if (arr[wR] == 0)

                zeroCount++;

                wR++;

            }

      

            // If zero count of current window is more than m,

            // reduce the window from left

            if (zeroCount > m)

            {

                if (arr[wL] == 0)

                zeroCount--;

                wL++;

            }

      

            // Update widest window if this window size is more

            if ((wR-wL > bestWindow) && (zeroCount<=m))

            {

                bestWindow = wR-wL;

                bestL = wL;

            }

        }

      

        // Print positions of zeroes in the widest window

        for (int i=0; i<bestWindow; i++)

        {

            if (arr[bestL+i] == 0)

            System.out.print(bestL+i + " ");

        }

    }