Max Consecutive Ones III

Understanding the Problem

This problem uses a "sliding window" strategy.

Given an array of binary, what is the longest length of consecutive "1"s we can return given our ability to flip "k" number of "0"s.

Consider the following:

array = [1, 1, 1, 0];
k = 0;
// return 3

array = [1, 1, 1, 0];
k = 1;           
// return 4 as we are able to flip 1 zero

Solution in Pseudocode

Keep track of the "max" length, which we will set to 0.

Keep track of a "left" pointer, which we will set to 0.

Keep track of an allotted "bank" of zeros that we can flip. The current bank is k flips, so we will set this to k.

Iterate accross the array. For Each iteration:

• if we come across a 0, we'll deduct 1 from our bank of flippable zeros.

• If our bank of zeros ever drops below 0, we'll increment our "left" pointer. But before we do, we'll check if "left" is zero first. If it is, we'll add to our bank of zeros and increment left by 1. If "left" is not zero, simply increment.

• Lastly, set the max to whichever is larger:

  • the current value (which is 0 currently in our first iteration)

  • or whatever the subtracted value of right - left (+ 1 to account for indexing)

Return max once we've completed iterating through the array.

Solution in Code

var longestOnes = function(nums, k) {
    let max = 0
    let left = 0
    let currentZeroCount = k
    for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) {
      currentZeroCount -= 1
    }
    while (currentZeroCount < 0) {
      if (nums[left] === 0) {
        currentZeroCount += 1
      }
      left += 1
    }
    max = Math.max(max, right - left + 1)
    }
    return max
};