Max Consecutive Ones II
MicrosoftThe problem
Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.
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.
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.
**Input **: nums [1,1,0,0,1,1,0,0,1,1]
- 1 <= nums.length <= 105
- nums[i] is either 0 or 1.
cpp
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
// Your code goes here
}
};java
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
// Your code goes here
}
}python
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# Your code goes here
return 0javascript
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function(nums) {
// Your code goes here
};csharp
public class Solution
{
public int FindMaxConsecutiveOnes(int[] nums)
{
// Your code goes here
}
}go
func findMaxConsecutiveOnes(nums []int) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Keep a window with at most one zero.
- 02Expand the right pointer.
- 03Count zeros in the current window.
- 04Shrink from the left while zeros exceed one.
- 05Track the widest valid window.
Reference answer
Then expect these follow-ups
How would you allow k flips?
Tests: generalization
How would you return the flipped index?
Tests: state tracking
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question