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 <= 105nums[i]is either0or1.
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 whetherzeroCountexceedsk.- If
zeroCountis greater thank, it necessitates shifting theleftboundary of the window to the right to exclude a zero and thereby maintain the constraint of at mostkzeroes within the window. Should the element being excluded (nums[left]) be a zero, decrementzeroCountby one. - Conversely, if
zeroCountdoes not exceedk, leverage the current window size to potentially update the result (res), signifying the maximum length of subarray achievable under the flipping constraint.
- If
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
leftboundary should shift when the window needs to exclude a zero to adhere to thekflips 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 } -
function findMaxConsecutiveOnes(nums: number[]): number { let [l, cnt] = [0, 0]; for (const x of nums) { cnt += x ^ 1; if (cnt > 1) { cnt -= nums[l++] ^ 1; } } return nums.length - l; } -
/** * @param {number[]} nums * @return {number} */ var findMaxConsecutiveOnes = function (nums) { let [l, cnt] = [0, 0]; for (const x of nums) { cnt += x ^ 1; if (cnt > 1) { cnt -= nums[l++] ^ 1; } } return nums.length - l; };