Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.
Example 1:
Input: nums = [1,0,1,1,0] Output: 4 Explanation: Flip the first zero will get the maximum number of consecutive 1s. After flipping, the maximum number of consecutive 1s is 4.
Example 2:
Input: nums = [1,0,1,1,0,1] Output: 4
Constraints:
1 <= nums.length <= 10^5nums[i] is either 0 or 1.
The description was taken from https://leetcode.com/problems/max-consecutive-ones-ii/.
#O(N) Time, O(1) Space
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
window, max_window = 0, 0
left, right = 0, 0
while right < len(nums):
window += nums[right]
right += 1
while window + 1 < right - left:
window -= nums[left]
left += 1
max_window = max(max_window, right - left)
return max_windowThis problem is a variation of Minimum Swaps to Group All 1s Together.
Within this problem, we are looking for a specific subarray; a subarray with the maximum number of ones and only one zero.
If we are given a problem that requires looking for a specific subarray or sublist that follows a certain constraint, that makes the problem a candidate for a sliding window.
To solve this, we can keep a running sum for our window and if that window sum ever becomes less than the distance between the two pointers minus one, then that means we have two zeros in our window so we should shrink the left side.
Let's start by creating two counters for the number of ones in the current window, and the maximum window we have seen so far.
We will also need a left and right pointer.
window, max_window = 0, 0
left, right = 0, 0
We will continue sliding our window until we have reached the end of the array.
while right < len(nums):
We will start each iteration off by adding the number at the right pointer to the window counter within each iteration.
Then, we will expand the window.
window += nums[right]
right += 1
Similar to traditional sliding window problems, we will expand our window until it no longer satisfies a given constraint and becomes invalid, in which case we will shrink the left side.
In this case, our window will no longer be valid if its length becomes greater than the window sum plus one because that would mean there are two zeros between the left and right pointers.
If that is the case, whatever window we were considering prior to the first zero within our window is invalid so we should evict the entire left side up to and including the first zero.
[1,0,1,1,1,0]
To do this, we will shrink the window by excluding the left pointer's number and incrementing the left pointer.
while window + 1 < right - left:
window -= nums[left]
left += 1
Once we have shrunk our window to a valid subarray, we will compare it to the maximum window we have saved, updating the maximum window if it is greater.
max_window = max(max_window, right - left)
When we have found the maximum window with the most ones and a single zero, we will return it.
return max_window