Leetcode problem 112 - Max Consecutive Ones III

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.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  // Initialize the left pointer for the sliding window
  let left = 0;

  // Initialize the maximum count of consecutive 1's
  let maxCount = 0;

  // Initialize the count of zeros within the current window
  let zeroCount = 0;

  // Iterate through the array using the right pointer
  for (let right = 0; right < nums.length; right++) {
    // Check if the current element is a zero and increment the zeroCount
    if (nums[right] === 0) {
      zeroCount++;
    }

    // Check if the number of zeros within the window exceeds the allowed flips (k)
    while (zeroCount > k) {
      // Move the left pointer to the right to reduce the window size
      // and decrement the zeroCount if the leftmost element is a zero
      if (nums[left] === 0) {
        zeroCount--;
      }
      left++;
    }

    // Update the maximum count of consecutive 1's by considering the current window size
    maxCount = Math.max(maxCount, right - left + 1);
  }

  // Return the maximum count of consecutive 1's considering the allowed flips (k)
  return maxCount;
};

The time complexity of this algorithm is O(n), where n is the length of the input array nums. This is because we iterate through the array once with the right pointer, and the left pointer can also move at most n times.

The space complexity is O(1) because we only use a constant amount of extra space to store the left pointer, maxCount, and zeroCount variables.