O(n) time and O(k) space Very Easy Solution for Any K Flips and Stream Input


  • 5

    It is similar to the Stock Buy and Sell K Times problem. We can use dynamic programming to solve this problem.

    Supposed that we can flip k zeros, and we use cnt[k] to represents the maximum length if we flip exactly k zeros.
    So cnt[0] is the maximum length if we do not flip any zero.

    If we encounter a '1', then every cnt[i] (0 <= i <= k) should increase one.

    If we encounter a '0', since cnt[k] means we already flip k times, so we can not flip any more zero, this the current maximum length, we update the result by "res = max(res, cnt[k])". For cnt[k-1], we still can flip one zero, do it, then we can update cnt[k] by "cnt[k] = cnt[k-1] + 1". In this way, we can update all cnts except cnt[0]. In fact, cnt[0] shuld be 0.

    After processing all numbers from the stream, we need look at all cnts and update result if there is a bigger number.

        int findMaxConsecutiveOnes(vector<int>& nums) {
            int k = 1; // flip at most k zeros
            vector<int> cnt(k + 1, 0);
            int res = 0;
            
            for (int i: nums) {
                if (i == 1) {
                    for (int &c: cnt) {
                        ++c;
                    }
                } else {
                    res = max(res, cnt[k]);
                    for (int j = k; j > 0; --j) {
                        cnt[j] = 1 + cnt[j - 1];
                    }
                    cnt[0] = 0;
                }
            }
            
            for (int i: cnt) {
                res = max(res, i);
            }
            
            return res;
        }
    

Log in to reply
 

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