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.
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.
}
}