Algorithm
Problem Name: 1004. Max Consecutive Ones III
Problem Link: https://leetcode.com/problems/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.
Constraints:
1 <= nums.length <= 105nums[i]is either0or1.0 <= k <= nums.length
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const longestOnes = function (A, K) {
let i = 0
let j = 0
const len = A.length
while (j < len) {
if (A[j] === 0) K--
if (K < 0) {
if (A[i] === 0) K++
i++
}
j++
}
return j - i
}
Input
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output
6
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestOnes(self, A: List[int], K: int) -> int:
zeros, res = [-1] + [i for i, c in enumerate(A) if not c] + [len(A)], 0
for j in range(K + 1, len(zeros)):
res = max(res, zeros[j] - zeros[j - K - 1] - 1)
return res or K and len(A)
Input
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output
6