Two pointers and sliding window

1004. Max Consecutive Ones III

Explanation

We can use a sliding window to solve this problem.

j is point to the leftmost zero position. At the beginning, we can make it point to -1 and pretend the -1.

Each time, if we meet with 0, K will be decreased by 1. If K is already 0, and we meet with zero, we must move to the first zero that j reach when increasing j step by step. As we are computate the result by using i — j it means that j is not included. So if j can point to the first zero, it reaches, then K will not be reduced to -1 as the left part exclude a 0.

You can go over the following example

/*
         k = 2
   ret:      3 4 3 3 2 3
     k:2 2 1 0 0 0 0 0 0
     i   0 1 2 3 4 5 6 7
                 |  
         1 0 0 1 0 0 0 1
         */

Code

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        const int n = nums.size();
        if (k >= n) return n;
         /*
         k = 2
   ret:      3 4 3 3 2 3
     k:2 2 1 0 0 0 0 0 0
     i   0 1 2 3 4 5 6 7
                 |  
         1 0 0 1 0 0 0 1
         */
        int ret = k;
        for (int i = 0, j = -1; i < n; ++i){
            if (nums[i] == 0) {
                // we don't have enough k, we have to move j to the first zero
                if (k == 0) {
                    while (true){
                        j++;
                        if (nums[j] == 0) break;
                    }
                } else k--;
            }
            ret = max(ret, i - j);
        }
        return ret;
    }
};

Thanks for reading.