1004. Max Consecutive Ones III

Problem Statement :

Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length Solution : Pepcoding Solution

Next Leetcode question is derivative of this question: DO TRY! 1493. Longest Subarray of 1’s After Deleting One Element

This question is based on Acquire and Release Strategy.

This question is basically asking to calculate the longest length of subarrays containing at-most k zeros!!

Solution:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int start = 0, end = 0;
        int maxLength = 0;
        int zeroCount = 0; // To keep track of the number of zeros in the current window
 
        while (end < nums.length) {
            // Expand the window by including nums[end]
            if (nums[end] == 0) {
                zeroCount++;
            }
 
            // Case 1: Window size is less than or equal to k (valid window)
            while (zeroCount > k) {
                // If the number at start is 0, reduce zeroCount
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++; // Shrink the window from the left
            }
 
            // Case 2: Process the current valid window
            maxLength = Math.max(maxLength, end - start + 1);
 
            end++; // Expand the window to the right
        }
 
        return maxLength; // Return the maximum length found
    }
 
}