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


  • 5

    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;
        }
    }

  • 0
    R

    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
    

  • 0
    K

    @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);
        }
    }```

Log in to reply
 

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