Welcome to Subscribe On Youtube

487. Max Consecutive Ones II

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.

 

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

 

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.

 

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?

Solutions

Suppose the problem statement allows for up to k flips of zeroes to ones. In such scenarios, adopting a versatile solution becomes paramount for addressing this variant efficiently. The strategy involves maintaining a sliding window [left, right] that encompasses at most k zeroes. Here’s an enhanced explanation:

  • Sliding Window: Utilize a dynamic window [left, right] to traverse through the array. This window expands or contracts based on the condition related to zeroes within it.

  • Handling Zeroes: As the window encounters a zero, increment a counter that tracks the number of zeroes (zeroCount). Subsequently, evaluate whether zeroCount exceeds k.

    • If zeroCount is greater than k, it necessitates shifting the left boundary of the window to the right to exclude a zero and thereby maintain the constraint of at most k zeroes within the window. Should the element being excluded (nums[left]) be a zero, decrement zeroCount by one.
    • Conversely, if zeroCount does not exceed k, leverage the current window size to potentially update the result (res), signifying the maximum length of subarray achievable under the flipping constraint.

Follow-up

In follow-up scenarios where direct access to prior elements via nums[left] may not suffice or be efficient, an alternative approach is advocated:

  • Zeroes Position Queue: Maintain a queue to record the positions of encountered zeroes. This queue becomes instrumental in precisely determining the next position to which the left boundary should shift when the window needs to exclude a zero to adhere to the k flips constraint.

This queue-based approach ensures that adjustments to the window’s left boundary are made with full knowledge of zeroes’ positions, thus optimizing window adjustments and maintaining the integrity of the k flips constraint.

Summary

The refined solution not only caters to the basic requirement of flipping up to k zeroes but also elegantly addresses more complex scenarios presented in follow-up questions. By systematically managing the sliding window and accurately tracking zeroes’ positions, this approach offers a robust and scalable solution to variants of the original problem.

  • class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int l = 0, r = 0;
        int k = 1;
        while (r < nums.length) {
            if (nums[r++] == 0) {
                --k;
            }
            if (k < 0 && nums[l++] == 0) {
                ++k;
            }
        }
        return r - l;
    }
}

  • class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int l = 0, r = 0;
        int k = 1;
        while (r < nums.size()) {
            if (nums[r++] == 0) {
                --k;
            }
            if (k < 0 && nums[l++] == 0) {
                ++k;
            }
        }
        return r - l;
    }
};

  • from collections import deque

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:

        res, zero, left, k = 0, 0, 0, 1

        for right in range(len(nums)):
            if nums[right] == 0:
                zero += 1
            while zero > k:
                if nums[left] == 0:
                    zero -= 1
                left += 1
            res = max(res, right - left + 1) # max-check every for iteration

        return res

class Solution: # followup, extra space
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:

        res, left, k = 0, 0, 1
        q = deque()

        for right in range(len(nums)):
            if nums[right] == 0:
                q.append(right)
            if len(q) > k:
                left = q.popleft() + 1
            res = max(res, right - left + 1) # max-check every for iteration

        return res

############

# maintain a sliding window of size 2, that keeps track of the counts.
class Solution: # follow up, optimized
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        count = 0  # Count of consecutive ones
        prev_count = 0  # Count of consecutive ones before a zero
        max_count = 0  # Maximum count of consecutive ones

        for num in nums:
            if num == 1:
                count += 1
                prev_count += 1
            else:
                count = prev_count + 1
                prev_count = 0

            max_count = max(max_count, count)

            # Reset the count and prev_count if we encounter two zeros in a row
            if num == 0 and prev_count == 0:
                count = 0
                prev_count = 0

        return max_count

############

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        l = r = 0
        k = 1
        while r < len(nums):
            if nums[r] == 0:
                k -= 1
            if k < 0:
                if nums[l] == 0:
                    k += 1
                l += 1
            r += 1
        return r - l

############

class Solution(object):
  def __init__(self):
    self.ans = 0
    self.count = 0
    self.lastCount = 0

  def findMaxConsecutiveOnes(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    for num in nums:
      self.readNum(num)  # stream the input
    return self.ans

  def readNum(self, num):
    """
    :type nums: int
    """
    if num == 1:
      self.count += 1
    else:
      self.count = self.count - self.lastCount + 1
      self.lastCount = self.count
    self.ans = max(self.ans, self.count)


  • func findMaxConsecutiveOnes(nums []int) int {
	l, r := 0, 0
	k := 1
	for ; r < len(nums); r++ {
		if nums[r] == 0 {
			k--
		}
		if k < 0 {
			if nums[l] == 0 {
				k++
			}
			l++
		}
	}
	return r - l
}

All Problems

All Solutions