Java clean solution easily extensible to flipping k zero and follow-up handled


  • 85
    Y

    The idea is to keep a window [l, h] that contains at most k zero

    The following solution does not handle follow-up, because nums[l] will need to access previous input stream
    Time: O(n) Space: O(1)

        public int findMaxConsecutiveOnes(int[] nums) {
            int max = 0, zero = 0, k = 1; // flip at most k zero
            for (int l = 0, h = 0; h < nums.length; h++) {
                if (nums[h] == 0)                                           
                    zero++;
                while (zero > k)
                    if (nums[l++] == 0)
                        zero--;                                     
                max = Math.max(max, h - l + 1);
            }                                                               
            return max;             
        }
    

    Now let's deal with follow-up, we need to store up to k indexes of zero within the window [l, h] so that we know where to move l next when the window contains more than k zero. If the input stream is infinite, then the output could be extremely large because there could be super long consecutive ones. In that case we can use BigInteger for all indexes. For simplicity, here we will use int
    Time: O(n) Space: O(k)

        public int findMaxConsecutiveOnes(int[] nums) {                 
            int max = 0, k = 1; // flip at most k zero
            Queue<Integer> zeroIndex = new LinkedList<>(); 
            for (int l = 0, h = 0; h < nums.length; h++) {
                if (nums[h] == 0)
                    zeroIndex.offer(h);
                if (zeroIndex.size() > k)                                   
                    l = zeroIndex.poll() + 1;
                max = Math.max(max, h - l + 1);
            }
            return max;                     
        }
    

    Note that setting k = 0 will give a solution to the earlier version Max Consecutive Ones

    For k = 1 we can apply the same idea to simplify the solution. Here q stores the index of zero within the window [l, h] so its role is similar to Queue in the above solution

        public int findMaxConsecutiveOnes(int[] nums) {
            int max = 0, q = -1;
            for (int l = 0, h = 0; h < nums.length; h++) {
                if (nums[h] == 0) {
                    l = q + 1;
                    q = h;
                }
                max = Math.max(max, h - l + 1);
            }                                                               
            return max;             
        }
    

  • 0
    A

    @yuxiangmusic
    Very neat and enlightening solution ! Thanks for sharing. BTW, have you ever considered how to leverage your philosophy here to address the follow-up challenge ? Since your code basically needs to examine partial previous input stream, I think it doesn't meet the follow-up requirement yet.


  • 2
    Y

    @Allen_Tung Thanks for pointing that out, I have added another approach to deal with follow-up


  • 0
    N

    for the solution 1, neat in logic, concise in naming,


  • 0
    A

    @yuxiangmusic
    Excellent complement ! Already bookmarked your solution : )
    Thanks again !


  • 1

    @yuxiangmusic Brilliant solutions. Want to give you two up-votes if I could :)


  • 0
    B

    You can use queue to do this though Queue is implemented by LinkedList


  • 1
    Y

    @Bigbear1991 Updated. Thanks.


  • 0
    T

    Same solution as posted by OP. I have tried to simplify it for the noobs like me. Can anyone simplify the algorithm description?

        /**
         * Algorithm:
         * k is most bits you can flip.
         * Use two indexes/pointers say high and low and a counter 'zero'.
         * zero counter : counts number of zeros seen till then.
         * high index checks for zeros and increments zero counter.
         * low index is only active when zero counter is greater than k and decrements zero counter when it encounters zero.
         *
         *
         * @param nums
         * @return
         */
        public static int findMaxConsecutiveOnes(int[] nums) {
            int max = 0, zero = 0, k = 2; // flip at most k zero
            int low = 0;
            for (int high = 0; high < nums.length; high++) {
                if (nums[high] == 0) {
                    zero++;
                }
                while (zero > k) {
                    if (nums[low] == 0) {
                        zero--;
                    }
                    low++;
                }
                max = Math.max(max, high - low + 1);
            }
            return max;
        }
    

  • 0
    T

    @yuxiangmusic
    I see that algorithm is trying to find a window of atleast k+1 zeroes.
    Why should it find k+1 zeroes instead of k zeroes?
    ie why while( zero>k ) instead of while( zero>=k )? Can you help?


  • 2
    Y

    The while loop says while the window contains more than k zeros, we should advance l until the window contains exactly k zeros.


  • 0
    T

    @yuxiangmusic thank you.


  • 0

    you can use 2 counters, one counter has already used it's zero flip and the other has not. When you see a zero the one that has already used it's flip must reset and the one that has not yet used it it's zero uses it now. The counter which is lesser is the the one that has not used it's zero. Also you can limit your check for max to when you see a zero and at the end.

        public int FindMaxConsecutiveOnes(int[] nums) 
        {
            int c1 = 0;
            int c2 = 0;
            int max = 0;
            
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] == 1)
                {
                    c1++;
                    c2++;
                }
                else if (c1 < c2)
                {
                    max = Math.Max(max, c2);
                    c1++;
                    c2 = 0;
                }
                else
                {
                    max = Math.Max(max, c1);
                    c1 = 0;
                    c2++;
                }
            }
            
            max = Math.Max(max, c1);
            max = Math.Max(max, c2);
            return max;
        }
    

  • 0

    In the solution for stream input, numbers in stream could be infinity, if you keep adding l and h, it might overflow.

    Some one should add a test case, where the size of input should be greater than the size of int/long (which seems impossible, LoL) @1337c0d3r


  • 2
    Y

    @0x0101 In the most extreme case, even the output max can overflow because there could be super long consecutive ones. In that case we have to use BigInteger not only for l and h but also for the output.

    Since the length of nums will not exceed Integer.MAX_VALUE we know l and h will never overflow for this problem. If we really want to deal with infinite input stream, then the method should be changed to:

    public BigInteger findMaxConsecutiveOnes(InputStream in);
    

  • 0

    brilliant idea !!! Very nice solutions for follow up questions.


  • 1
    J

    I came up with a solution very similar to yours.

    class Solution(object):
        def findMaxConsecutiveOnes(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            maximum, seqLen, lastZero = 0, 0, -1
            for i, n in enumerate(nums):
                if n == 1:
                    seqLen += 1
                else:
                    seqLen = i - lastZero
                    lastZero = i
                maximum = max(maximum, seqLen)
            return maximum
    

  • 3
    I

    @yuxiangmusic You dont need max for every number, just do it when 0 is seen. Reduced to 8 ms, beats 98%.

            int prev = -1, cur = -1, ans = 0;
            for (int i = 0; i < nums.length; ++i) {
                if (nums[i] == 0) {
                    ans = Math.max(ans, i - prev - 1);
                    prev = cur;
                    cur = i;
                }
            }
            return Math.max(ans, nums.length - prev - 1);
    
    

  • 0
    A

    what if the question asked as to swap the values of two different positions only once and get max consecutive 1's sub array length?


  • 0
    F

    I came up with a similar idea. Use variable index to record the position of zero, and initiate the index to -1. Once we find a zero, refresh the count and store the new index.

    public class Solution {
        public int findMaxConsecutiveOnes(int[] nums) {
            int max = 0, count = 0, index = -1;
            for(int i = 0;i< nums.length; i++){
                if(nums[i] == 1){
                    count++;
                }else{
                    count = i - index;
                    index = i;
                }
                max = Math.max(max,count);
            }
            return max;
        }
    }
    

Log in to reply
 

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