Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1004.html
Level
Medium
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 <= A.length <= 20000
0 <= K <= A.length
A[i]
is0
or1
Solution
It is best to use a general solution to deal with this kind of problem. A window [left,right]
can be maintained to hold at least k zeros
. When it encounters 0, it accumulates the number of zero, and then judges
- if the number of 0 is greater than
k
at this time, then shifts the left boundary left to the right, - and if the removed
nums[left]
is 0, then zero decrements by 1. - If it is not greater than
k
, use the number of digits in the window to updateres
.
Code
Java
-
public class Max_Consecutive_Ones_III { class Solution { public int longestOnes(int[] nums, int k) { int res = 0, zero = 0, left = 0; for (int right = 0; right < nums.length; ++right) { if (nums[right] == 0) ++zero; while (zero > k) { if (nums[left++] == 0) --zero; } res = Math.max(res, right - left + 1); } return res; } } }
-
// OJ: https://leetcode.com/problems/max-consecutive-ones-iii/ // Time: O(N) // Space: O(1) class Solution { public: int longestOnes(vector<int>& A, int k) { int i = 0, j = 0, cnt = 0, N = A.size(), ans = 0; while (j < N) { cnt += A[j++] == 0; while (cnt > k) cnt -= A[i++] == 0; ans = max(ans, j - i); } return ans; } };
-
class Solution: def longestOnes(self, nums: List[int], k: int) -> int: l = r = -1 while r < len(nums) - 1: r += 1 if nums[r] == 0: k -= 1 if k < 0: l += 1 if nums[l] == 0: k += 1 return r - l ############ # 1004. Max Consecutive Ones III # https://leetcode.com/problems/max-consecutive-ones-iii/ class Solution: def longestOnes(self, nums: List[int], k: int) -> int: n = len(nums) i = 0 for j in range(n): if nums[j] == 0: k -= 1 if k < 0: if nums[i] == 0: k += 1 i += 1 return j - i + 1
Loop over the array and store the start index of the subarray and the number of zeros in the subarray.
Initially, the start index start
is 0, and the number of zeros zerosCount
is 0. For each index i
from 0 to A.length - 1
, if A[i] == 0
, then increase zerosCount
by 1. As long as zerosCount <= K
, all zeros met so far can be changed to ones. If at one step zerosCount > K
, then move start
forward until the number of zeros in the subarray (from index start
to index i
) is not more than K
. At each index i
, update the max consecutive ones using i - start + 1
. Finally, return the max consecutive ones.
-
class Solution { public int longestOnes(int[] A, int K) { int max = 0; int start = 0; int zerosCount = 0; int length = A.length; for (int i = 0; i < length; i++) { int num = A[i]; if (num == 0) zerosCount++; while (zerosCount > K) { if (A[start] == 0) zerosCount--; start++; } max = Math.max(max, i - start + 1); } return max; } }
-
// OJ: https://leetcode.com/problems/max-consecutive-ones-iii/ // Time: O(N) // Space: O(1) class Solution { public: int longestOnes(vector<int>& A, int k) { int i = 0, j = 0, cnt = 0, N = A.size(), ans = 0; while (j < N) { cnt += A[j++] == 0; while (cnt > k) cnt -= A[i++] == 0; ans = max(ans, j - i); } return ans; } };
-
class Solution: def longestOnes(self, nums: List[int], k: int) -> int: l = r = -1 while r < len(nums) - 1: r += 1 if nums[r] == 0: k -= 1 if k < 0: l += 1 if nums[l] == 0: k += 1 return r - l ############ # 1004. Max Consecutive Ones III # https://leetcode.com/problems/max-consecutive-ones-iii/ class Solution: def longestOnes(self, nums: List[int], k: int) -> int: n = len(nums) i = 0 for j in range(n): if nums[j] == 0: k -= 1 if k < 0: if nums[i] == 0: k += 1 i += 1 return j - i + 1