[Leetcode] 1004. Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/description/

initial

so I was close but my thinking of every solution seems to be:

once we get right condition -> we update answer.

But we can actually think broadly and

we update answer along the way -> once we get invalid condition we adjust it (like moving the pointers to make current window valid) to make it valid

my initial attempt was doing the former. But the condition is wrong. its not count==k thats not the right condition. We can have count less than k and that is the right condition too read the q properly. So lets try to think of the latter way.

wrong initial attempt

class Solution {
    public int longestOnes(int[] nums, int k) {
        int count = 0;
        int left = 0;
        int right = 0;
        int n = nums.length;
        int ans = 0;
        while (left < n && right < n) {
            if (nums[right] == 0)
                count += 1;
            while (count == k) {
                ans = Math.max(ans, right - left + 1);
                if (nums[left] == 0) {
                    count -= 1;
                }
                left += 1;
            }
            right += 1;
        }
        ans += (k - count);
        return ans;
    }
}

solution

so we are updating the answer along the way and once count becomes bigger than k, that is invalid case. SO we shift left pointer to the left until we get valid case.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int count=0;int left=0;int right=0; int n = nums.length;
        int ans =0;
        while(right<n){
            if(nums[right]==0)count+=1;
            while(count>k){
                if(nums[left]==0){
                    count-=1;
                }
                left+=1;
            }
            ans=Math.max(ans,right-left+1);
            right+=1;
        }
        return ans;
    }
}

complexity

n time
1 space