Algorithm Practice: Max Consecutive Ones II

Today we are going to go over how to solve a Medium difficulty algorithm problem used by Zillow for technical interviews called Max Consecutive Ones II. This was my first Medium difficulty LeetCode question and I had a very difficult time with coming up and understanding the solution, I hope this can help you understand the problem a little faster than I did.

Problem

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

Example 1:

Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
    After flipping, the maximum number of consecutive 1s is 4.

Note:

• The input array will only contain 0 and 1.
• The length of input array is a positive integer and will not exceed 10,000

Solutions

Approach 1: Brute Force

Algorithm

Let’s start simple and work our way up.

A brute force solution usually involves trying to check every single possibility. It’ll look something like this:

• Check each and every possible consecutive sequence
• Count how many 0’s are in each sequence. If there are two zeros encountered in a window, break
• If our sequence has one or fewer 0’s, check if that’s the longest consecutive sequence of 1's.

var findMaxConsecutiveOnes = function(nums) {
    let max = 0;
    for (let left = 0; left < nums.length; left++) {
        let zeroCount = 0;
        for(let right = left; right < nums.length; right++) {
            if (nums[right] === 0) {
                zeroCount++;
            }
            if (zeroCount <= 1) {
                max = Math.max(max, right - left + 1);
            } else break;
        }
       
    }
     return max;
};

Complexity Analysis

Let n be equal to the length of the input nums array.

• Time complexity : O(n²). The nested for loops turn our approach into a quadratic solution because for every index, we have to check every other index in the array.
• Space complexity : O(1). We are using 4 variables: left, right, zeroCount, max. The number of variables are constant and do not change based on the size of the input.

Approach 2: Sliding Window

Intuition

We saw with the brute force solution, checking every single consecutive sequence is not optimal. Intuitively, we know we’re doing repeated work because sequences overlap. We are checking consecutive sequence blindly. We need to establish some rules on how to move our sequence forward. Let’s see how we can optimize the code we just wrote using a sliding window (two pointer) algorithm.

• If our sequence is valid, let’s continue expanding our sequence (because our goal is to get the largest sequence possible).
• If our sequence is invalid, let’s stop expanding and contract our sequence (because an invalid sequence will never count towards our largest sequence).

The pattern that comes to mind for expanding/contracting sequences is the sliding window. Let’s define valid and invalid states.

• Valid State = one or fewer 0’s in our current sequence
• Invalid State = two 0’s in our current sequence

Algorithm

Great. How do we apply all this to the sliding window?

Let’s use left and right pointers to keep track of the current sequence a.k.a. our window. Let’s expand our window by moving the right pointer forward until we reach a point where we have more than one 0 in our window. When we reach this invalid state, let’s contract our window by moving the left pointer forward until we have a valid window again. By expanding and contracting our window from valid and invalid states, we are able to traverse the array efficiently without repeated overlapping work.

Now we can break this approach down into a few actionable steps:

While our window is in bounds of the array…

1. Add the rightmost element to our window
2. Check if our window is invalid. If so, contract the window until valid.
3. Update our the longest sequence we’ve seen so far
4. Continue to expand our window

var findMaxConsecutiveOnes = function(nums) {
    let ones = 0, prevOnes = 0;
    let zeroes = 0, hasZero = false;
    let max = 0;
    
    for (let k of nums) {
        if (k) {
            ones++;
            zeroes = 0;
        } else {
            hasZero = true;
            prevOnes = (++zeroes === 1) ? ones : 0;
            ones = 0;
        }
        max = Math.max(max, hasZero * prevOnes + hasZero + ones);
    }
    return max;
};

Complexity Analysis

Let n be equal to the length of the input nums array.

• Time complexity : O(n). Since both the pointers only move forward, each of the left and right pointer traverse a maximum of n steps. Therefore, the time complexity is O(n).
• Space complexity : O(1). Same as the previous approach. We don’t store anything other than variables. Thus, the space we use is constant because it is not correlated to the length of the input array.

Conclusion

We can see that using a sliding window or two pointer method can save us a lot of time and complexity.

I hope you liked my different methods of solving this problem. Please let me know if you have a different way of solving the problem or if you see something wrong with my solution.