487. Max Consecutive Ones II

MediumArrayDynamic ProgrammingSliding Window
Leetcode Link

Problem Description

The problem is about finding the longest sequence of consecutive 1s in a binary array, under the condition that we are allowed to flip at most one 0 to 1. This task tests our ability to manipulate subarrays in a binary context and optimize our approach to account for small alterations in the array to achieve the desired outcome.

Intuition

To find the solution to this problem, we look to a two-pointer approach. Essentially, we're trying to maintain a window that can include up to one 0 to maximize the length of consecutive ones.

Let's think of this as a sliding window that starts from the left end of the array and expands to the right. As we move the right pointer (r) through the array, we keep track of the number of 0s we've included in the window. We initialize k to 1, because we're allowed to flip at most one 0.

When we encounter a 0, we decrement k. If k becomes negative, it means we've encountered more than one zero, and thus, we need to shrink our window from the left by moving the left pointer (l) to the right.

We continue expanding and shrinking the window as needed to always maintain at most one 0 within it. Throughout the process, we keep track of the maximum window size we've seen, which gives us the longest sequence of consecutive 1s with at most one 0 flipped.

When we have finished iterating through the array with our right pointer, the length of the window (r - l) is our maximum number of consecutive 1s, accounting for flipping at most one 0. The code does not explicitly keep a maximum length variable; instead, it relies on the fact that the window size can only increase or stay the same throughout the iteration, because once the window shrinks (when k becomes negative), it will then begin to expand again from a further position in the array.

Learn more about Dynamic Programming and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution uses a two-pointer technique to efficiently find the maximum length of a subarray with consecutive 1s after at most one 0 has been flipped.

Here is a step-by-step breakdown of the implementation:

  1. Initialize two pointers, l and r, to point at the start of the array. These pointers represent the left and right bounds of our sliding window, respectively.
  2. Define a variable k with an initial value of 1, which represents how many 0s we can flip. Since we are allowed to flip at most one 0, we start with k = 1.
  3. Iterate through the array by moving the right pointer r towards the end. This loop continues until r reaches the end of the array.
  4. Within the loop, check if the current number pointed to by r is a 0. If it is, decrement k.
  5. If k becomes less than 0, it signifies that our window contains more than one 0, which is not allowed. Thus, we need to increment l, our left pointer, to narrow the window and possibly discard a 0 from the window:
    • Inside another loop, we check if the number at the current l position is a 0. If it is, we increment k because we are "flipping" the 0 back and excluding it from the current window.
    • Then, we move l one step to the right by increasing its value by 1.
  6. Increment r each time to examine the next element in the array.
  7. After the while loop exits, calculate the length of the current window (r - l). Since the right pointer has reached the end of the array, this value equals the maximum size of the window we found throughout our traversal.

Important notes regarding the code and algorithm:

  • There is no need to explicitly keep track of the maximum window size during the loop because the window can only grow or maintain its size. It shrinks only when necessary to exclude an excess 0.

  • The solution leverages the problem constraint. Knowing that only one 0 can be flipped, it eliminates the need for complex data structures or algorithms. A straightforward integer (k) is enough to keep track of the condition being met.

  • This solution has a time complexity of O(n) where n is the length of the array. This is because each element is checked once by the right pointer r.

  • The space complexity of this algorithm is O(1) as it operates with a constant number of extra variables regardless of the input size.

By keeping the algorithm simple and avoiding unnecessary data structures, the solution remains elegant and efficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let’s use a small example to illustrate the solution approach. Consider the binary array [1, 0, 1, 1, 0, 1, 1, 1, 0, 1], where we are allowed to flip at most one 0 to achieve the longest sequence of 1s.

Following the solution steps:

  1. Initialize two pointers l and r to 0 (the start of the array).

  2. Set k to 1 since we can flip at most one 0.

  3. As we start iterating with r, the subarray from l to r initially grows without any issue since the first element is a 1.

  4. When r=1, the element is 0. We decrement k to 0 because we used our allowance to flip a 0.

  5. We continue to move r. The window now has consecutive 1s and looks like this: [1, 1 (flipped), 1, 1].

  6. At r=4, we encounter another 0 and k is already 0. Now we must shrink the window from the left. We move l one step to the right. The subarray does not contain zero at l=1, hence no change in k.

  7. Moving l again to 2, we encounter our previously flipped 0. We increment k back to 1.

  8. The window is now [1, 1, 0, 1, 1] from l=2 to r=5, and we can flip the 0 at r=4 because k=1.

  9. We continue this process, moving r to the end, and each time we hit a 0 with k=0, we shift l to maintain only one flipped 0.

  10. At the end, when r is just past the end of the array, the length of the window is calculated by r - l, giving us the longest sequence of consecutive 1s where at most one 0 was flipped.

In this example, the longest subarray we can form after flipping at most one 0 is [1, 1, 0 (flipped), 1, 1, 1] which starts at l=2 and ends just before r=8, resulting in a length of 6.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
5        # Initialize the left and right pointers
6        left_pointer = right_pointer = 0
7        zero_count = 1  # Variable to allow flipping of one '0' to '1'
8
9        # Traverse the array while the right_pointer is within the array bounds
10        while right_pointer < len(nums):
11            # Decrease zero_count when a '0' is encountered 
12            if nums[right_pointer] == 0:
13                zero_count -= 1
14              
15            # If zero_count is less than 0, slide the window to the right 
16            # by moving the left_pointer to the next position
17            if zero_count < 0:
18                # When we move the left_pointer forward, we need to check if 
19                # we are passing over a '0' and if so, increase zero_count
20                if nums[left_pointer] == 0:
21                    zero_count += 1
22                # Move the left pointer to the right
23                left_pointer += 1
24              
25            # Move the right pointer to the right
26            right_pointer += 1
27          
28        # The length of the longest subarray of 1's (possibly with one flipped 0)
29        # is the difference between the right and left pointers.
30        return right_pointer - left_pointer
31
1class Solution {
2    public int findMaxConsecutiveOnes(int[] nums) {
3        int left = 0; // Initialize the left pointer
4        int right = 0; // Initialize the right pointer
5        int zerosAllowed = 1; // Initialize the number of zeros allowed to flip to ones
6
7        // Loop through the array using the right pointer
8        while (right < nums.length) {
9            // If the current element is 0, decrement the number of zeros allowed
10            if (nums[right++] == 0) {
11                zerosAllowed--;
12            }
13            // If no zeros are allowed and the left element is 0, increment the left pointer
14            // and the number of zeros allowed
15            if (zerosAllowed < 0 && nums[left++] == 0) {
16                zerosAllowed++;
17            }
18        }
19        // Compute the length of the longest sequence of 1s (with at most one 0 flipped to 1)
20        return right - left;
21    }
22}
23
1#include<vector>
2
3class Solution {
4public:
5    int findMaxConsecutiveOnes(vector<int>& nums) {
6        int left = 0; // Left pointer for the window
7        int right = 0; // Right pointer for the window
8        int zeroCount = 1; // Initial max number of zeroes allowed to flip
9      
10        int maxConsecutive = 0; // Variable to store the maximum length of consecutive ones
11      
12        // Iterate over the array
13        while (right < nums.size()) {
14            // If we encounter a zero, decrement zeroCount
15            if (nums[right] == 0) {
16                zeroCount--;
17            }
18          
19            right++; // Expand the window to the right
20          
21            // If zeroCount is negative, it means we have encountered
22            // more than one zero in our window. We then need to shrink
23            // the window from the left
24            while (zeroCount < 0) {
25                if (nums[left] == 0) { // If we're moving past a zero, increment zeroCount
26                    zeroCount++;
27                }
28                left++; // Shrink the window from the left
29            }
30          
31            // Calculate the length of the current window and update maxConsecutive if it's larger
32            int windowLength = right - left;
33            maxConsecutive = max(maxConsecutive, windowLength);
34        }
35      
36        return maxConsecutive; // Return the maximum length of consecutive ones found
37    }
38};
39
1function findMaxConsecutiveOnes(nums: number[]): number {
2    let left = 0; // Left pointer for the sliding window
3    let right = 0; // Right pointer for the sliding window
4    let zeroCount = 1; // Number of zeroes allowed to flip (fixed at one according to the problem)
5
6    let maxConsecutive = 0; // To store the maximum length of consecutive ones
7
8    // Iterate over 'nums' using the right pointer as the leader of the sliding window
9    while (right < nums.length) {
10        // If a zero is encountered, decrement 'zeroCount'
11        if (nums[right] === 0) {
12            zeroCount--;
13        }
14      
15        // Move the right pointer to the right, expanding the window
16        right++;
17      
18        // If 'zeroCount' is less than 0, more than one zero has been encountered
19        // Start shrinking the window from the left until 'zeroCount' is not negative
20        while (zeroCount < 0) {
21            // If we move past a zero on the left, increment 'zeroCount'
22            if (nums[left] === 0) {
23                zeroCount++;
24            }
25            // Increment the left pointer to shrink the window from the left
26            left++;
27        }
28      
29        // Calculate the current window length
30        const windowLength = right - left;
31      
32        // Keep track of the maximum length of ones encountered
33        maxConsecutive = Math.max(maxConsecutive, windowLength);
34    }
35  
36    // Return the maximum number of consecutive ones found
37    return maxConsecutive;
38}
39
Not Sure What to Study? Take the 2-min Quiz：

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input list nums. This efficiency is achieved because the code uses a two-pointer technique that iterates through the list only once. The pointers l (left) and r (right) move through the array without making any nested loops, thus each element is considered only once during the iteration.

The space complexity of the code is O(1), which means it uses constant additional space regardless of input size. No extra data structures that grow with the input size are used; the variables l, r, and k take up a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫