Max Consecutive Ones III

Description

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s. 

 

Example 1:

Input: A = [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: A = [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.

 

Note:

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1 

Solution(javascript)

/* eslint-disable no-loop-func */
/*
 * @lc app=leetcode id=1004 lang=javascript
 *
 * [1004] Max Consecutive Ones III
 */

// @lc code=start

// /** Top-down Time Limit Exceeded
//  * @param {number[]} A
//  * @param {number} K
//  * @return {number}
//  */
// const longestOnes = function (A, K) {
//   const aux = (index, sum, count) => {
//     if (index >= A.length) {
//       return sum
//     }
//     if (A[index] === 0) {
//       let max = Math.max(
//         aux(index + 1, 0, 1), sum,
//       )
//       if (count <= K) {
//         max = Math.max(
//           aux(index + 1, sum + 1, count + 1),
//           max,
//         )
//       }
//       return max
//     }
//     return aux(index + 1, sum + 1, count)
//   }
//   return aux(0, 0, 1)
// }

// /** Sliding window
//  * @param {number[]} A
//  * @param {number} K
//  * @return {number}
//  */
// const longestOnes = function (A, K) {
//   let max = 0
//   let left = 0
//   let right = 0
//   let currentK = K
//   let currentMax = 0
//   while (right < A.length) {
//     if (A[right] === 1) {
//       currentMax += 1
//       right += 1
//     } else if (currentK > 0) {
//       currentK -= 1
//       currentMax += 1
//       right += 1
//     } else {
//       while (left <= right) {
//         currentMax -= 1
//         if (A[left] === 0) {
//           currentK = 1
//           left += 1
//           break
//         } else {
//           left += 1
//         }
//       }
//     }
//     max = Math.max(max, currentMax)
//   }
//   return max
// }
/** Sliding window 2
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
const longestOnes = function (A, K) {
  let max = 0
  let left = 0
  let currentK = K

  for (let right = 0; right < A.length; right++) {
    if (A[right] === 0) {
      currentK -= 1
    }
    while (currentK < 0) {
      if (A[left] === 0) {
        currentK += 1
      }
      left += 1
    }
    max = Math.max(max, right - left + 1)
  }
  return max
}
// @lc code=end