Well explained O(n) time & O(1) space solution for max consecutive ones I && II


  • 0
    C

    Max Consecutive Ones I:

    We can solve this with 1D DP, the state currentLen[i] means the consecutive ones ending with index i.

    So naturally, we have following induction relationship between currentLen[i] and currentLen[i-1]:
    currentLen[i] = currentLen[i-1] //if nums[i] == 1
    currentLen[i] = 0 //if nums[i] == 0

    To get the maximum length, we just need to on-the-fly do maxing on currentLen[i] and the global max.

    Note that currentLen[i] is only related to currentLen[i-1] so we can use one variable instead of an array.

        int findMaxConsecutiveOnes(vector<int>& nums) {
            int maxLen = 0;
            int currLen = 0;
            for (int i=0; i<nums.size(); i++) {
                currLen = (nums[i] == 0) ? 0 : currLen+1;
                maxLen = max(maxLen, currLen);
            }
            return maxLen;
        }
    

    Max Consecutive Ones II

    We still solve this by 1D DP and a scan from left to right. Now at each number the the length of consecutive ones sequence may be resulted from flipping one '0' or no flipping any.

    So the states now becomes:
    flipLen[i] = length of consecutive ones ending at index [i] with one bit flipped in between [0, i]
    noFlipLen[i] = length of consecutive ones ending at index[i] with on bits flipped between [0, i].

    Naturally the induction relationship is now:
    flipLen[i] = flipLen[i-1] + 1 //if nums[i] == 1
    noFlipLen[i] = noFlipLen[i-1] + 1 //if nums[i] == 1

    flipLen[i] = noFlipLen[i-1] + 1 //if nums[i] == 0
    noFlipLen[i] = 0 //if nums[i] == 0

    And we can keep a global maxLen by on-the-flying best-casing maxLen vs flipLen[i].

    Also both flipLen[i] and noFlipLen[i] are only related to [i-1] we can use two variables to keep track of them.

        int findMaxConsecutiveOnes(vector<int>& nums) {
            int flipLen = 0;
            int noFlipLen = 0;
            int maxLen = 0;
            for (int i=0; i<nums.size(); i++) {
                if (nums[i] == 1) {
                    flipLen += 1;
                    noFlipLen += 1;
                } else {
                    flipLen = noFlipLen + 1;
                    noFlipLen = 0;
                }
                maxLen = max(max(flipLen, noFlipLen), maxLen);
            }
            return maxLen;
        }
    

Log in to reply
 

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