Max Consecutive Ones III

#dsa #programming #cpp #productivity

🧠 Intuition:
We are given a binary array

(0s and 1s),
and an integer k which represents the maximum number of 0s we can flip to 1s.
We need to find the maximum number of consecutive 1s in the array if we are allowed to flip at most k 0s.

This is a sliding window problem. The idea is to maintain a window [left, right] such that at most k zeros are in the window. As we expand the window to the right, if the count of zeros exceeds k, we shrink it from the left until we have at most k zeros again.

🔍 Approach (Using Sliding Window):
Initialize two pointers: left = 0 and right = 0, and a variable zeros = 0 to count the number of 0s in the current window.

Start expanding the window by moving right:

If nums[right] == 0, increment zeros.

While zeros > k, shrink the window from the left:

If nums[left] == 0, decrement zeros.

Move left++.
At each step, calculate the window length: right - left + 1 and track the maximum.

Complexity
Time complexity:
O(n)

Space complexity:
O(1)

Code

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
       int n = nums.size();
       int left = 0;

       for(int right = 0;right<n;right++){
        if(nums[right] == 0){
            k--;
        }

        if(k < 0){
            if(nums[left] == 0){
                k++;
            }
            left++;
        }
       }

       return n - left;
    }
};

📁 Organized DSA Repository
I've started a DSA-in-C++ GitHub repository where all problems are sorted algorithm-wise into folders like: