Sliding window+2 pointers,O(n) time 1 pass,O(1) space

• I learned this from the decent tutorial by @zjh08177,thank you !! https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

``````public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int j=0;
int len=0;
int zero=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
zero++;
}

while(zero>1){
if(nums[j]==0){
zero--;
}
j++;
}
len=Math.max(i-j+1,len);
}

return len;
}
}``````

• Best and simplest solution out there! Thanks for the link!

Here's a Python version:

``````class Solution(object):
def findMaxConsecutiveOnes(self, nums):
zero, mx, j = 0, 0, 0
for i in xrange(0, len(nums)):
if nums[i] == 0:
zero += 1
while zero > 1:
if nums[j] == 0:
zero -= 1
j += 1
mx = max(mx, i - j + 1)
return mx
``````

• @bxiao0801 Cool solution. I thought of this one myself. I don't think it uses any specific techniques. I just came up with it purely from scratch. It's O(n) time (one pass) and O(1) space.

``````public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
// used to store the index of the start of the current sequence of 1s, not including any flips
int start = -1;

// used to indicate whether or not we can flip
boolean flip = true;

// used to store the length of the current sequence of 1s that can be created, possibly including a flip
int length = 0;

// used to store the max value of "length" seen so far
int max = 0;

for (int i = 0; i < nums.length; i ++)
{
int curr = nums[i];

if (curr == 0)
{
if (flip)
{
flip = false;
length ++;
start = -1;
}
else
{
max = Math.max(max, length);
if (start == -1) {
length = 0;
flip = true;
} else {
length = i - start + 1;
flip = false;
start = -1;
}
}
}
else
{
if (start == -1)
{
start = i;
}
length ++;
}
}

max = Math.max(max, length);
return Math.min(nums.length, max);
}
}`````````

• @bxiao0801

Rigorously speaking, this is not a 1 pass solution (or at least, it does not solve the follow-up question with stream input) because: in your code block,

``````            while(zero>1){
if(nums[j]==0){
zero--;
}
j++;
}
``````

you need to access `noms[j]` where `j` can be far from `i` such that `num[j]` is unavailable with stream input.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.