1004. Max Consecutive Ones III

Description

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 <= 105
  nums[i] is either 0 or 1.
  0 <= k <= nums.length

Solution from others

 
// using sliding window
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function longestOnes(nums, k) {
  let left = 0; // Initialize the left boundary of the window
  let right; // Initialize the right boundary of the window
  let maxLen = 0; // Variable to store the maximum length of consecutive 1's
 
  for (right = 0; right < nums.length; right++) {
    // If the current number is 0, decrement k
    if (nums[right] === 0) {
      k--;
    }
 
    // If k becomes negative, i.e., we have flipped more than k 0's to 1's
    // Move the left boundary of the window to the right, adjusting k accordingly
    while (k < 0) {
      if (nums[left] === 0) {
        k++;
      }
      left++;
    }
 
    // Update the maximum length of consecutive 1's
    // The size of the current window is right - left + 1
    maxLen = Math.max(maxLen, right - left + 1);
  }
 
  return maxLen;
}

Explanation

1. Goal: This function aims to find the longest stretch of consecutive 1s in an array after flipping at most k zeros to 1s.
2. Inputs:

• nums: An array of 1s and 0s.
• k: The maximum number of 0s that can be flipped to 1s.

3. Initial Setup:

• left: Marks the starting point of our current window of numbers.
• right: This will mark the end of our current window as we iterate through the array.
• maxLen: Tracks the longest sequence of 1s we've found so far.

4. Iterating Through the Array: With a for-loop, we examine each element in the nums array from start to end (right goes from 0 to the end of the array).
5. Handling 0s:

• Each time we encounter a 0 (nums[right] === 0), we reduce k by 1 because we're "using up" one of our allowed flips.
• If k becomes negative, it means we've flipped more 0s than allowed. To fix this, we move the left boundary of our window to the right until k is no longer negative, effectively "unflipping" a 0 back to its original state if necessary.

6. Calculating the Max Length: After each iteration (move of the right boundary), we calculate the size of the current window (right - left + 1) and update maxLen if this window is larger than any we've seen before.
7. Result: Once we've examined all elements in the array, the function returns maxLen, the size of the longest sequence of 1s possible with up to k flips from 0 to 1.