Posts Max Consecutive Ones II
Post
Cancel

Max Consecutive Ones II

PROBLEM DESCRIPTION

Given a binary array nums, return the maximum number of consecutive 1’s in the array if you can flip at most one 0.

leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {

    public int findMaxConsecutiveOnes(int[] nums) {
        int n = nums.length;

        int i = 0;            // left pointer i to the beginning of the window.
        int j = 0;            // right pointer j to the end of the window.

        int flipped = 0;      // Initialize a variable to keep track of the number of flips made.

        int maxLength = 0;

        // While there are no elements left in nums array (tracked using j pointer which is the end of the window)
        while (j < n) {

            // If the current element at j is 1, it's a consecutive one.
            if (nums[j] == 1) {

                // Increment the current consecutive ones length and move the right pointer.
                maxLength = Math.max(maxLength, j - i + 1);
                j++;

            } else {  // If the current element at j is 0, we need to consider a flip.

                // If we haven't used our flip yet (flipped is 0):
                if (flipped == 0) {

                    // Increment the current consecutive ones length as we can flip the current 0 to 1.
                    maxLength = Math.max(maxLength, j - i + 1);

                    flipped = 1;  // Set flipped to 1 to indicate that we've used our flip.
                    j++;         // Move the right pointer to the next element.

                } else {  // If we've already used our flip:

                    // reduce the window from left side until we get a 0
                    // when we are at that position, we know we must have flipped it already (because "flipped" is 1 at this point)
                    // at that point, we can reset flip and start from the next position after that 0
                    // note that, we have not incremented j at this point. So, flipped is still 0. In the next iteration, nums[j] will be 0 and flipped=0, in which case we will cover flipping this position as well.
                    // alternatively, we can increment j here and keep flipped as 1. That will also work.
                    while (nums[i] == 1) {
                        i++;
                    }
                    flipped = 0;  // Reset flipped to 0, as we are going to flip a 0.
                    i++;         // Move the left pointer to the next element to consider a flip.

                }

            }

        }

        return maxLength;  // Return the maximum consecutive ones length with at most one flip.

    }

}
This post is licensed under CC BY 4.0 by the author.