Leetcode 487. Max Consecutive Ones II

Problem Explanation:

The problem is about finding the maximum number of consecutive 1s in a binary array where we have the possibility to flip at most one 0 to 1. The array will only contain 0s and 1s, and the length of the array will not exceed 10,000. For this problem, we can view flipping a 0 to 1 as essentially extending a sequence of 1s across a single 0.

Approach:

The approach taken in the solution utilizes a combination of the sliding window method and the two pointer technique, where the window represents the maximum sequence of 1s (including at most one 0).

Instead of keeping track of the number of 1s in the window, we actually keep track of the number of 0s. We start with the left and right pointers at the start of the array.

We then add to 'r' as we move the right pointer along the array. If we stumble upon a 0, we increment the zeros counter. If the zeros counter becomes 2, we move the left pointer 'l' forward, decrementing the zeros counter if a 0 is found.

Finally, the maximum consecutive ones sequence can be calculated as the difference between the right and left pointers + 1. We use this calculation to update the answer with the maximum sequence length at each step.

Example:

Let's consider an example,

In the case of the array [1, 0, 1, 1, 0]

• In the initial state, the l and r pointers are at position 0 and zeros is 0.Notice that whenever we encounter 0, we increase zeros to 1.

• Then our array state becomes [0, 1, 1, 0].

• Now we try to advance 'r' to next position, but zeros becomes 2.

• We would advance 'l' until zeros becomes 1 again. Now our array state becomes [1, 1, 0].

• We then continue to increase 'r' and our final array state becomes [1, 0, 1] and answer becomes 3.

• We then advance to next and our array state becomes [0, 1, 0] and answer becomes 2.

After going through every element in array, our final answer becomes 4.

Python solution:

1
2python
3
4class Solution():
5    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
6        n=len(nums)
7        l=0
8        r=0
9        zeros=0
10        ans=0
11        while r<n:
12            if(nums[r]==0):
13                zeros+=1
14            while zeros==2:
15                if(nums[l]==0):
16                    zeros-=1
17                l+=1
18            ans=max(ans,r-l+1)
19            r+=1
20        return ans
21

Java Solution:

1
2java
3public class Solution {
4   public int findMaxConsecutiveOnes(int[] nums) {
5     int zeros = 0, l = 0; 
6     int max = 0;
7     for (int r = 0; r < nums.length; r++) {
8       if (nums[r] == 0) zeros++;
9       while (zeros == 2) {
10         if (nums[l++] == 0) zeros--;
11       }
12       max = Math.max(max, r - l + 1);
13     }
14     return max;
15   }
16}
17

Javascript Solution:

1
2javascript
3var findMaxConsecutiveOnes = function(nums) {
4    let l = 0;
5    let r = 0;
6    let zeros = 0;
7    let max = 0;
8    while (r < nums.length) {
9        if (nums[r] === 0) {
10            zeros++;
11        }
12        while (zeros === 2) {
13            if (nums[l++] === 0) {
14                zeros--;
15            }
16        }
17        max = Math.max(max, r - l + 1);
18        r++;
19    }
20    return max;
21};
22

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int findMaxConsecutiveOnes(vector<int>& nums) {
6        int l = 0, r = 0, zeros = 0, max = 0;
7        while (r < nums.size()) {
8            if (nums[r] == 0) zeros++;
9            while (zeros == 2) {
10                if (nums[l++] == 0) zeros--;
11            }
12            max = std::max(max, r - l + 1);
13            r++;
14        }
15        return max;
16    }
17};
18

C# Solution:

1
2csharp
3public class Solution {
4    public int FindMaxConsecutiveOnes(int[] nums) {
5        int l = 0, r = 0, zeros = 0, max = 0;
6        while (r < nums.Length) {
7            if (nums[r] == 0) zeros++;
8            while (zeros == 2) {
9                if (nums[l++] == 0) zeros--;
10            }
11            max = Math.Max(max, r - l + 1);
12            r++;
13        }
14        return max;
15    }
16}
17

R Solution:

1
2r
3findMaxConsecutiveOnes <- function(nums) {
4    l <- 1
5    r <- 1
6    zeros <- 0
7    max < -0
8    while (r <= length(nums)) {
9        if (nums[r] == 0) {
10            zeros <- zeros + 1
11        }
12        while (zeros == 2) {
13            if (nums[l] == 0) {
14                zeros <- zeros - 1
15            }
16            l <- l + 1
17        }
18        max = max(max, r - l + 1)
19        r <- r + 1
20    }
21    return (max)
22}

In the R solution, we have a similar pattern using two pointers for traversal. However, the length(nums) function is used to give the array's length, r starts at 1 since R uses 1-based indexing, and we use the "<-" symbol for assignment instead of an equals sign. The nums[r] and nums[l] is used to get the r-th and l-th elements of the array nums. The max function is used to compute the maximum of the two quantities and return is used to return the result from the function.

Swift Solution:

1
2swift
3class Solution {
4    func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
5        var l = 0, r = 0, zeros = 0, max = 0
6        while r < nums.count {
7            if nums[r] == 0 { zeros += 1 }
8            while zeros == 2 {
9                if nums[l] == 0 { zeros -= 1 }
10                l += 1
11            }
12            max = Swift.max(max, r - l + 1)
13            r += 1
14        }
15        return max
16    }
17}

In Swift, we use similar syntax to both Java and Python. Swift provides an inbuilt max function, 'Swift.max()', to calculate the maximum of two quantities. 'count' is used to give the array's length. The "_ nums: [Int]" portion refers to the fact that the function is expecting an array of integers as an input. 'nums[r]' and 'nums[l]' are used to get the r-th and l-th elements of the array nums.

In summary, the solutions in different programming languages all follow similar logic but may use syntax specific to that language. These examples show how this problem can be solved using some popular languages including Python, Java, Javascript, C++, C#, R and Swift. This single problem solution provides insight on how same logic can be implemented in various programming languages.